1.两数之和（乱序）

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 leetcode 1

  1. 输入：nums = [2,7,11,15], target = 9
  2. 输出：[0,1]
  3. 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

思路分析：

  1. 利用HashMap 存储元素到索引的映射（num -> index），降低时间复杂度
  2. 存在相同元素时，后面元素的索引会覆盖前面的索引

  3. 遍历时从前往后，若存在相同元素，通过i得到前面元素，通过map得到后面元素

    1.  public int[] twoSum(int[] nums, int target) {
    2.      HashMap<Integer,Integer> map = new HashMap<>();
    3.      int[] res = new int[2];
    5.      for(int i = 0 ; i < nums.length; i++){
    6.          //存在相同元素时，后面元素的索引会覆盖前面的索引
    7.          map.put(nums[i],i);
    8.      }
    10.      for(int i = 0 ; i < nums.length; i++){
    11.          int sub = target - nums[i];
    12.          //遍历时从前往后，若存在相同元素，通过i得到前面元素，通过map得到后面元素
    13.          if(map.containsKey(sub) && map.get(sub) != i){
    14.             res = new int[]{i,map.get(sub)};
    15.          }
    16.      }
    18.      return res;
    19.  }

    2.N数之和（排序）

题目描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 leetcode 15 leetcode 18 

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

双指针 + 递归

  • N为2时，可以利用双指针技巧找到目标和
  • N大于2时，先计算两数之和，然后将两数之和看作整体 再与第三个数计算求和

  • 利用start控制双指针寻找的范围

    //计算n数之和
public List<List<Integer>>  NSum(int[] nums,int n,int start,int target) {
  List<List<Integer>> res = new ArrayList<>();    

  // n == 2时，两数之和，双指针解法。排序 + while去重
  if(n == 2){
      int left = start;
      int right = nums.length - 1;
      while(left < right){
          int leftVal = nums[left];
          int rightVal = nums[right];
          int sum = leftVal + rightVal;

          if(sum < target){
              //去重
              while(left < right && leftVal == nums[left]) left++;
          }

          else if(sum > target){
              while(left < right && rightVal == nums[right]) right--;
          }
          else{
              ArrayList<Integer> path = new ArrayList<>();
              path.add(leftVal);
              path.add(rightVal);

              res.add(path);
              while(left < right && leftVal == nums[left]) left++;
              while(left < right && rightVal == nums[right]) right--;
          }

      }
  }
  // n > 2时，递归调用
  else{
      for(int i = start; i < nums.length;i++){
          List<List<Integer>> minus = NSum(nums,n - 1,i + 1,  target - nums[i]);

          for(List<Integer> m : minus){
              m.add(nums[i]);
              res.add(m);
          }

          while(i < nums.length  - 1 && nums[i] == nums[i + 1]) i++;
      }
  }

  return res;
}

    2.最接近的三数之和

    题目描述

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 leetcode 16

排序 + 双指针 + 去重

  • 思路与N数之和相同，先计算两数之和，再将两数之和看作整体 再与第三个数计算求和

  • 因为是求 最接近的和，在每次求和时，需要将求得的sum与target进行比较，不断更新sum

    public int threeSumClosest(int[] nums, int target) {

      Arrays.sort(nums);
      int closest = 30000;

      for(int i = 0 ; i < nums.length - 2; i ++){
          int sum = nums[i] + twoSumClosest(nums, target - nums[i], i + 1);
          if(Math.abs(sum - target) < Math.abs(closest - target)){
              closest = sum;
          }
      }

      return closest;
  }

  public int twoSumClosest(int[] nums, int target,int start){
      int left = start;
      int right = nums.length - 1;
      int closest = 30000;

      while(left < right){
          int leftVal = nums[left];
          int rightVal = nums[right];
          int sum = leftVal + rightVal;

          //每次计算时，更新sum和与 最接近的结果
          if(Math.abs(sum - target) < Math.abs(closest - target)){
              closest = sum;
          }

          if(sum < target){
              while(left < right && nums[left] == leftVal){
                  left++;
              }
          }

          else if(sum > target){
              while(left < right && nums[right] == rightVal){
                  right--;
              }
          }
          else{
              return target;
          }
      }

      return closest;
  }