I would recommend that you review ACI 201.2R-77 (Reapproved 1982) titled "Guide to Durable Concrete". It contains recommended air contents for frost-resistant concrete. For example,according to this guide: IF nominal maximum aggregate size is 1 1/2 inch the average air content should be 5 1/2 percent for outdoor exposure in a cold climate where the concrete may be in almost continuous contact with moisture prior to freezing, or where deicing salts are used (e.g., pavements, bridge decks, sidewalks, and watertanks).
Note: The ACI guide states that there is conflicting opinion whether air contents lower than those given in its recommendation table (which the above example came from) should be permitted for high strength (5500 psi) concrete.
The ACI guide has another table that recommends for seawater exposure, concrete with Type II, IP(MS), or IS(MS) cement.
In the "Proposed revision of: Guide to Durable Concrete" (ACI 201.2R-92), section 2.3-Seawater exposure, states (in part) ...concrete should reach a maturity equivalent of not less than 5000 psi at 28 days when fully exposed to seawater."
The FEMA Coastal Construction Manual (FEMA 55, June 2000) recommends (for construction in area subject to saltwater flooding) using 5000 psi minimum compressive strength (for durability).
You should also check-out your local building code and your regional building code (e.g., IBC).
In my very limited experience with concrete, I have only seen concrete with Type V cement used in fishing-piers that are constantly exposed/submerged in saltwater.