Two Sum

• when it is not sorted

  • HashMap，存放值和index, 注意pair的index不可以相同 map.get(b) != i。可以只需要一次循环

• when it is sorted

  int left = 0, right = nums.length - 1;
  int count = 0;
  while (left < right) {
    if (nums[left] + nums[right] <= target 满足某个条件) {
        left++;
    } else {
        //count += right - left;
        right--;
    }
  }
  

  3 Sum

• i 取到nums.length - 2的前一个即可，因为3sum，第一个for循环里面i表示的是选择的第一个数
• 需要跳过重复的

  if (i > 0 && num[i] == num[i-1])
            continue;
  

  在第一次获得i时候，就要进行跳过检验 用两个while语句分别检查lo和hi

  while (lo < hi && num[lo] == num[lo+1]) lo++;
  while (lo < hi && num[hi] == num[hi-1]) hi--;
  

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>();
    for (int i = 0; i < num.length-2; i++) {
        if (i > 0 && num[i] == num[i-1])
            continue;
        int lo = i+1, hi = num.length-1, sum = 0 - num[i];
        while (lo < hi) {
            if (num[lo] + num[hi] == sum) {
                res.add(Arrays.asList(num[i], num[lo], num[hi]));
                while (lo < hi && num[lo] == num[lo+1]) lo++;
                while (lo < hi && num[hi] == num[hi-1]) hi--;
                lo++; hi--;
            } else if (num[lo] + num[hi] < sum) lo++;
            else hi--;
        }
    }
    return res;    
}

3 Sum Closet

找到最接近target的3sum

• i 取到nums.length - 2的前一个即可，因为3sum，第一个for循环里面i表示的是选择的第一个数
• 无需担心重复的数字（不用跳过）

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result = 0;
        int gap = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {

            int left = i+1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else {
                    left++;
                }

                if (Math.abs(sum - target) < gap) {
                    gap = Math.abs(sum - target);
                    result = sum;
                }                 
            }
        }

        return result;
    }
}

3 Sum Smaller

• 区别
  1. 求的是可能的组合的个数（这里并没有要求值不能重复）
  2. 在<target的情况下，left和right都有可能变化，这个时候就要注意到题目所求的不同。因为需要的是求解的可能个数，所以可以直接通过count+=right-left来求的，这就涵盖了left不变 right--的情况

类似的还有valid triangle number唯一不同的是，这时候为了确保left和right只有一个需要移动，i从array末端开始取，即最大值

4 Sum

比3Sum多一层循环而已，注意在中间的循环也要去重，并且同样是要排除第一个if (j > i+1 && nums[j] == nums[j-1]) continue;