1、两数之和
本题使用哈希法，用一个哈希Map保存数组的值以及对应下标，代码如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(map.containsKey(target-nums[i])){
return new int[] {i,map.get(target-nums[i])};
}
map.put(nums[i],i);
}
return new int[] {-1,-1};
}
}2、字母异位词分组
本题使用哈希法，使用哈希表存储每一组字母异位词，键为这组异位词的标志(将字符串排序后的字符串作为键)，值为这组字母异位词形成的列表。
代码如下：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str : strs){
char[] array = str.toCharArray();//将字符串转化成字符数组，方便排序
Arrays.sort(array);
String key = new String(array);//将排序后的字符数组转回字符串，当作哈希表的键
List<String> list = map.getOrDefault(key,new ArrayList<String>());//从哈希表取出当前键对应的值，若无则默认返回一个数组列表
list.add(str);//将当前字符串加入数组列表
map.put(key,list);
}
return new ArrayList<>(map.values());
}
}3、最长连续序列
考虑到数组中可能有重复元素需要去重，并且有查找操作，可以使用HashSet集合，既可以去除重复元素，又方便进行查找操作。
遍历集合，如果有当前元素的后继元素，则序列长度++。 代码如下：
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> hashSet = new HashSet<>();
int ans = 0;
for(int num : nums){
hashSet.add(num);
}
for(int num : hashSet){
//有前驱元素直接跳过，因为此时肯定不是最长序列。
if(!hashSet.contains(num-1)){
int local_max = 1;
while(hashSet.contains(num+1)){
local_max += 1;
num += 1;
}
ans = Math.max(ans , local_max);
}
}
return ans;
}
}4、移动零
本题需要原地操作，使用双指针解决，快指针用于遍历旧数组，慢指针用于维护新数组。代码如下：
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0;
int slow = 0;
while(fast < nums.length){
if(nums[fast] == 0){
fast++;
}
else{
nums[slow] = nums[fast];
slow++;
fast++;
}
}
for(int i=slow; i<nums.length; i++){
nums[i] = 0;
}
}
}5、盛最多水的容器
本题利用双指针分别指向数组头和尾，然后用一个变量保存最大面积，每记录一次，让指针移动一格，这里比较关键的点就是要让height值比较低的那个指针移动，最后当两个指针相碰时，结束循环 。
代码如下：
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length-1;
int ans = 0;
while(left < right){
ans = Math.max(ans , (right-left)*Math.min(height[left],height[right]));
if(height[left] < height[right]){
left++;
}
else{
right--;
}
}
return ans;
}
}6、三数之和
本题采用排序+双指针的解法，关键点是需要去重，代码如下：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
if(i>0 && nums[i]==nums[i-1]) continue;
int left = i+1;
int right = nums.length-1;
while(left < right){
if(left>i+1 && nums[left]==nums[left-1]){
left++;
continue;
}
if(right<nums.length-1 && nums[right]==nums[right+1]){
right--;
continue;
}
if(nums[i]+nums[left]+nums[right] < 0) left++;
else if(nums[i]+nums[left]+nums[right] > 0) right--;
else{
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
ans.add(list);
left++;
right--;
}
}
}
return ans;
}
}7、接雨水
经典题目接雨水，思路就是用两个数组 left 和 right 分别保存当前柱子左侧和右侧的最高柱子(第一个和最后一个柱子不需要保存)， 再分别求出每一列柱子能存储的水量。 代码如下：
class Solution {
public int trap(int[] height) {
int left[] = new int[height.length];
int right[] = new int[height.length];
int left_max = height[0];
int right_max = height[height.length-1];
int ans = 0;
//当前柱子左侧的最高柱子
for(int i=1; i<height.length-1; i++){
left[i] = left_max;
left_max = Math.max(left_max , height[i]);
}
//当前柱子右侧的最高柱子
for(int i=height.length-2; i>=1; i--){
right[i] = right_max;
right_max = Math.max(right_max,height[i]);
}
for(int i=1; i<height.length-1; i++){
int area = Math.max(0 , Math.min(left[i],right[i])-height[i]);
ans += area;
}
return ans;
}
}
