元素之和

一、两数之和

给定⼀个整数数组 nums 和⼀个⽬标值 target ，请你在该数组中找出和为⽬标值的那两个整数，并返回他们的数组下标。

你可以假设每种输⼊只会对应⼀个答案。但是，你不能重复利⽤这个数组中同样的元素。

示例:

给定 nums = [2, 7,11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1.1 哈希表

function twoSum(nums,target){
    const map = new Map();
    for(let i=0;i<nums.length;i++){
        const k = target - nums[i];
        if(map.has(k)){
            return [map.get(k),i]
        }
        map.set(nums[i],i);
    }
}

测试用例

const array = [3, 2, 4];
// const array = [1, 2, 7, 8, 11, 15];
const result = twoSum(array, 6);
console.log(result);

1.2 暴力枚举

function twoSum(nums,target){
    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];
            }
        }
    }
}

特点: 返回的结果比较灵活, 既可以是值，也可以是索引。

测试用例

const array = [3, 2, 4];
// const array = [1, 2, 7, 8, 11, 15];
const result = twoSum(array, 6);
console.log(result);

1.3 碰撞指针

function sortArray(nums) {
  let start = 0;
  let end = nums.length - 1;
  let stack = [[start, end]];
  while (stack.length > 0) {
    let range = stack.pop();
    if (range[0] >= range[1]) {
      continue;
    }
    let left = range[0];
    let right = range[1];
    let pivot = nums[left];
    while (left < right) {
      while (left < right && nums[right] > pivot) {
        right--;
      }
      while (left < right && nums[left] <= pivot) {
        left++;
      }
      [nums[left], nums[right]] = [nums[right], nums[left]];
    }
    [nums[range[0]], nums[left]] = [nums[left], nums[range[0]]];
    if (range[0] < right) {
      stack.push([range[0], left - 1]);
    }
    if (range[1] > left) {
      stack.push([right + 1, range[1]]);
    }
  }
  return nums;
}

function twoSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  const result = [];
  sortArray(nums);

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [nums[left], nums[right]];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
}

特点: 由于通过 sortArray 排序, 因此, 返回原数组需要额外的操作。

测试用例

const array = [3, 2, 4];
// const array = [1, 2, 7, 8, 11, 15];
const result = twoSum(array, 6);
console.log(result);

二、两数之和-不同组成

给定⼀个有序整数数组 nums 和⼀个⽬标值 target ，请你在该数组中找出和为⽬标值的那两个整数，并返回他们的数组下标。

你可以假设每种输⼊只会对应⼀个答案。但是，你不能重复利⽤这个数组中同样的元素。

示例:

给定 nums = [1, 2, 7, 8, 11, 15], target = 9
所以返回 [[1,8],[2,7]]

2.1 哈希表

function quickSort(array, start, end) {
  if (start >= end) {
    return;
  }
  let left = start;
  let right = end;
  let pivot = array[left];

  while (left < right) {
    while (left < right && array[right] > pivot) {
      right--;
    }
    while (left < right && array[left] <= pivot) {
      left++;
    }
    [array[left], array[right]] = [array[right], array[left]];
  }

  [array[start], array[left]] = [array[left], array[start]];
  quickSort(array, start, left - 1);
  quickSort(array, right + 1, end);
}

function sort(array) {
  quickSort(array, 0, array.length - 1);
}

function twoSum(array, target) {
  const map = new Map();
  const result = [];
  sort(array);

  let i = 0;
  while (i < array.length) {
    let value = array[i];
    let k = target - value;

    if (map.has(k)) {
      result.unshift([k, value]);
      while (value === array[i + 1]) {
        i++;
      }
      i++;
    } else {
      map.set(value, i);
      i++;
    }
  }

  return result;
}

测试用例

const array = [3, 2, 4];
// const array = [1, 2, 7, 8, 11, 15];
const result = twoSum(array, 6);
console.log(result);

2.2 碰撞指针

function sortArray(nums) {
  let start = 0;
  let end = nums.length - 1;
  let stack = [[start, end]];
  while (stack.length > 0) {
    let range = stack.pop();
    if (range[0] >= range[1]) {
      continue;
    }
    let left = range[0];
    let right = range[1];
    let pivot = nums[left];
    while (left < right) {
      while (left < right && nums[right] > pivot) {
        right--;
      }
      while (left < right && nums[left] <= pivot) {
        left++;
      }
      [nums[left], nums[right]] = [nums[right], nums[left]];
    }
    [nums[range[0]], nums[left]] = [nums[left], nums[range[0]]];
    if (range[0] < right) {
      stack.push([range[0], left - 1]);
    }
    if (range[1] > left) {
      stack.push([right + 1, range[1]]);
    }
  }
  return nums;
}

function twoSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  const result = [];
  sortArray(nums);

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      result.push([nums[left], nums[right]]);
      left++;
      right--;
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return result;
}

测试用例

// const array = [3, 2, 4];
const array = [1, 2, 7, 8, 11, 15];
const result = twoSum(array, 9);
console.log(result);

三、三数之和

给你⼀个包含 n 个整数的数组 nums ，判断 nums 中是否存在三个元素 a ， b ， c ，使得 a+ b + c = 0 ？请你找出所有满⾜条件且不重复的三元组。

注意：答案中不可以包含重复的三元组

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满⾜要求的三元组集合为：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

3.1 哈希表

思路:

数组排序
遍历数组，对每一元素采用 Set
去重

function threeSum(nums, target) {
    if (!nums || nums.length < 3) {
        return []
    }
    nums.sort((a, b) => a - b);
    let set = new Set();
    let result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > target) {
            break
        }
        while (nums[i] == nums[i - 1]) {
            i++;
        }
        let j = i + 1;
        while (j < nums.length) {
            let k = target - nums[i] - nums[j];
            if (set.has(k)) {
                result.push([nums[i], nums[j], k]);
                set.add(nums[j]);
                j++;
                while (nums[j] == nums[j - 1]) {
                    j++;
                }
            } else {
                set.add(nums[j]);
                j++
            }
        }
        set = new Set();
    }
    return result;
}

let nums = [-1, 0, 1, 2, -1, -4];
let target = 0;
console.log(threeSum(nums, target));

3.2 碰撞指针

思路:

数组排序
遍历数组，对每一元素采用双指针遍历
分别去重左右指针

function threeSum(nums, target) {
    if (!nums || nums.length < 3) {
        return []
    }
    nums.sort((a, b) => a - b);
    let set = new Set();
    let result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > target) {
            break
        }
        while (nums[i] == nums[i - 1]) {
            i++
        }
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            let l = nums[left];
            let r = nums[right];
            let sum = nums[i] + l + r;
            if (sum == target) {
                result.push([nums[i], l, r]);
                while (l == nums[left + 1]) {
                    left++;
                }
                while (r == nums[right - 1]) {
                    right--;
                }
                left++;
                right--;
            } else if (sum < target) {
                left++
            } else {
                right--
            }
        }
    }
    return result
}

let nums = [-1, 0, 1, 2, -1, -4];
let target = 0;
console.log(threeSum(nums, target));

四、四数之和

4.1 哈希表

思路:

数组排序
遍历数组，对每一元素采用 Set
去重

function fourSum(nums, target) {
    if (!nums || nums.length < 4) {
        return []
    }
    nums.sort((a, b) => a - b);
    let result = [];
    let set = new Set();
    for (let i = 0; i < nums.length - 3; i++) {
        if (nums[i] > target) {
            break
        }
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break
        }
        while (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
            i++
        }
        while (nums[i] == nums[i - 1]) {
            i++
        }
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break
            }
            while (nums[i] + nums[j] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
                j++
            }
            while (nums[j] == nums[j - 1]) {
                j++
            }
            let thecond = j + 1;
            while (thecond < nums.length) {
                let k = target - nums[i] - nums[j] - nums[thecond];
                if (set.has(k)) {
                    result.push([nums[i], nums[j], nums[thecond], k]);
                    set.add(nums[thecond]);
                    thecond++
                    while (nums[thecond] == nums[thecond - 1]) {
                        thecond++
                    }
                } else {
                    set.add(nums[thecond]);
                    thecond++
                }
            }
            set = new Set();
        }
    }
    return result
}

let nums = [1, 0, -1, 0, -2, 2];
let target = 0;
console.log(fourSum(nums, target));

4.2 碰撞指针

思路:

数组排序
遍历数组，对每一元素采用双指针遍历
分别去重左右指针

function fourSum(nums, target) {
    if (!nums || nums.length < 4) {
        return []
    }
    nums.sort((a, b) => a - b);
    let result = [];
    for (let i = 0; i < nums.length - 3; i++) {
        if (nums[i] > target) {
            break
        }
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break
        }
        while (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
            i++
        }
        while (nums[i] == nums[i - 1]) {
            i++
        }
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (nums[j] > target) {
                break
            }
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break
            }
            while (nums[i] + nums[j] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
                i++
            }
            while (nums[i] == nums[i - 1]) {
                i++
            }
            let left = j + 1;
            let right = nums.length;
            while (left < right) {
                let l = nums[left];
                let r = nums[right]
                let sum = nums[i] + nums[j] + l + r;
                if (sum == target) {
                    result.push([nums[i], nums[j], l, r]);
                    while (nums[left] == nums[left + 1]) {
                        left++
                    }
                    while (nums[right] == nums[right - 1]) {
                        right--
                    }
                    left++;
                    right--;
                } else if (sum < target) {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return result
}

let nums = [1, 0, -1, 0, -2, 2];
let target = 0;
console.log(fourSum(nums, target));

五、K 数之和

给定 n 个不同的正整数，整数 k（k <= n）以及一个目标数字 target。　在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？

输入: List = [1,2,3,4] ； k = 2 ； target = 5
输出: 2
说明: 1 + 4 = 2 + 3 = 5

思路:

设状态为f[i][j][p]，表示前i个数中找出j个数且和等于p的方案数目.
那么状态转移方程： f[i][j][p] = f[i - 1][j][p] + f[i - 1][j - 1][p -num[i]].
最终返回f[n][k][target]即可

function kSum(nums, k, target) {
    if (!nums || !nums.length || k <= 0) {
        return 0;
    }
    let result = [];
    for (let x = 0; x < nums.length + 1; x++) {
        result[x] = [];
        for (let y = 0; y < k + 1; y++) {
            result[x][y] = [];
            for (let z = 0; z < target + 1; z++) {
                result[x][y][z] = 0;
            }
        }
    }
    for (let i = 0; i < nums.length; i++) {
        result[i][0][0] = 1;
    }
    for (let x = 1; x <= nums.length; x++) {
        for (let y = 1; y <= k && y <= x; y++) {
        for (let z = 1; z <= target; z++) {
            result[x][y][z] = 0;
            if (z >= nums[x - 1]) {
                result[x][y][z] = result[x - 1][y - 1][z - nums[x - 1]];
            }
            result[x][y][z] += result[x - 1][y][z];
        }
        }
    }
    return result[nums.length][k][target];
}

const array = [1,2,3,4];
const k = 2;
const target = 5;
console.log(kSum(array, k, target));

六、长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例1:

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例2:

输入：target = 4, nums = [1,4,4]
输出：1

示例3：

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

6.1 暴力法

暴力法是最直观的方法。初始化子数组的最小长度为无穷大，枚举数组 nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从 nums[i] 到 nums[j] 的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是 j−i+1）

function minSubArray(target,nums){
    let len=nums.length;
    if(len==0){
    return 0
    }
    let result=Infinity;
    for(let i=0;i<len;i++){
    let sum=nums[i];
    if(sum>=target){
        return 1
    }
    for(let j=i+1;j<len;j++){
        sum+=nums[j];
        if(sum>=target){
        result=Math.min(result,j-i+1);
        break
        }
    }
    }
    return result==Infinity?0:result
}
const target=7;
const nums=[2,3,1,2,4,3];
// const target=11;
// const nums=[1,1,1,1,1,1,1,1];
// const target=4;
// const nums=[1,4,4];
console.log(minSubArray(target,nums));

性能分析:

时间复杂度：O(n2)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。

空间复杂度：O(1)。

6.2 滑动窗口

思路: 通过维护一个滑动窗口 nums[start,end] 来解决

定义 start 和 end 表示子数组（滑动窗口）的开始位置和结束位置
定义 sum 存储子数组中的元素和，初始值为 0
每一轮迭代(end<num.length)
- sum+=nums[end]
- 如果 sum>=target , 迭代更新子数组最小长度，窗口通过 start 向右移动
- 窗口通过 end 向右移动

function minSubArrayLen(target, nums) {
    let start=0;
    let end=0;
    let min=Infinity;
    let sum=0;
    while(end<nums.length){
        sum+=nums[end];
        while(sum>=target){
            min=Math.min(min,end-start+1);
            sum-=nums[start];
            start++;
        }
        end++;
    }
    return min==Infinity?0:min;
};

七、目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例1:

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例2:

输入：nums = [1], target = 1
输出：1

7.1 回溯

思路:

function findTargetSumWays(nums,target){
    let count=0;
    const backtrack=(nums,target,index,sum)=>{
        if(index===nums.length){
            if(sum==target){
            count++
            }
        }else{
            backtrack(nums,target,index+1,sum+nums[index]);
            backtrack(nums,target,index+1,sum-nums[index]);
        }
    }
    backtrack(nums,target,0,0);
    return count;
}

性能分析:

时间复杂度：O(2^n)，其中 n 是数组 nums 的长度。回溯需要遍历所有不同的表达式，共有 2^n 种不同的表达式，每种表达式计算结果需要 O(1) 的时间，因此总时间复杂度是 O(2^n)。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。空间复杂度主要取决于递归调用的栈空间，栈的深度不超过 n。

7.2 动态规划

思路:

function findTargetSumWays(nums,target){
    let sum=0;
    for(const num of nums){
        sum+=num;
    }
    const diff=sum-target;
    if(diff<0||diff%2!==0){
        return 0;
    }
    const neg=Math.floor(diff/2);
    const dp=new Array(neg+1).fill(0);
    dp[0]=1;
    for(const num of nums){
        for(let j=neg;j>=num;j--){
            dp[j]+=dp[j-num];
        }
    }
    return dp[neg];
}

性能分析:

时间复杂度：O(n×(sum−target))，其中 n 是数组 nums 的长度，sum 是数组 nums 的元素和，target 是目标数。动态规划有 (n+1)×((sum-target)/2+1) 个状态，需要计算每个状态的值。
空间复杂度：O(sum−target)，其中 sum 是数组 nums 的元素和，target 是目标数。使用空间优化的实现,需要创建长度为 ((sum-target)/2+1) 的数组 dp。

一、两数之和​

1.1 哈希表​

1.2 暴力枚举​

1.3 碰撞指针​

二、两数之和-不同组成​

2.1 哈希表​

2.2 碰撞指针​

三、三数之和​

3.1 哈希表​

3.2 碰撞指针​

四、四数之和​

4.1 哈希表​

4.2 碰撞指针​

五、K 数之和​

六、长度最小的子数组​

6.1 暴力法​

6.2 滑动窗口​

七、目标和​

7.1 回溯​

7.2 动态规划​

一、两数之和

1.1 哈希表

1.2 暴力枚举

1.3 碰撞指针

二、两数之和-不同组成

2.1 哈希表

2.2 碰撞指针

三、三数之和

3.1 哈希表

3.2 碰撞指针

四、四数之和

4.1 哈希表

4.2 碰撞指针

五、K 数之和

六、长度最小的子数组

6.1 暴力法

6.2 滑动窗口

七、目标和

7.1 回溯

7.2 动态规划