N数之和问题

2数之和 (求数组中的下标)

• 穷举

  var twoSum = function (nums, target) {
  if (nums.length < 2) {
    return [];
  }
  // 穷举
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  };

• Map

  var twoSum = function (nums, target) {
  if (nums.length < 2) {
    return [];
  }
  // Map
  let diffMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (diffMap.has(target - nums[i])) {
      return [i, diffMap.get(target - nums[i])];
    } else {
      diffMap.set(nums[i], i);
    }
  }
  };

  如果给出的数组是有序的，则可以直接使用双指针 - ”左右夹逼“

var twoSum = function(nums, target){
    if(nums.length < 2){
        return [];
    }
  let left = 0, right = nums.length-1;
    while(left < right){
          let sum = nums[left] + nums[right];
        if(sum === target){
          return [left, right]
      }
        if(sum < target){
          left++;
      }
            if(sum > target){
          right++;
      }
  }
}

3数之和(求数组中的元素)

4数之和(求数组中的元素)