剑指 Offer（专项突击版）第7|8题-烟雨网

theme: fancy

前言

现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第7|8题。

剑指 Offer II 007. 数组中和为 0 的三个数

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

难度：中等

示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。 
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。 

提示：
● 3 <= nums.length <= 3000
● -105 <= nums[i] <= 105

知识点： 数组双指针排序

方法一：双指针

这题是006的加强版。如果输入的数组是排序的，就可以先固定一个数字i，然后在排序数组中查找和为-i的两个数字。我们已经有了用O（n）时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是O（n^2）。

算法流程：

特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
对数组进行排序。
遍历排序后数组：

若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
1. 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
2. 若和大于 0，说明 nums[R] 太大，R 左移
3. 若和小于 0，说明 nums[L] 太小，L 右移

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums === null || len < 3) return [];
    // 排序
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len; i++) {
        if(nums[i] > 0) break;
        // 去重
        if(i > 0 && nums[i] === nums[i - 1]) continue;
        let L = i + 1;
        let R = len - 1;
        while (L < R) {
            const sum = nums[i] + nums[L] + nums[R];
            if(sum === 0) {
                ans.push([nums[i],nums[L],nums[R]]);
                while(L < R && nums[L] === nums[L + 1]) L++;
                while(L < R && nums[R] === nums[R - 1]) R--;
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }
    return ans;
};

复杂度分析

时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。
空间复杂度： O(1)：指针使用常数大小的额外空间。

剑指 Offer II 008. 和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums[l], nums[l+1], …, nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 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 

提示：
● 1 <= target <= 109
● 1 <= nums.length <= 105
● 1 <= nums[i] <= 105

知识点： 数组二分查找前缀和滑动窗口

方法一：滑动窗口

定义两个指针 P1 和 P2 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[P1]到 nums[P2] 的元素和）。

初始状态下，P1 和 P2 都指向下标 0，sum 的值为 0。

当指针P1和P2之间的子数组数字之和小于k时，向右移动指针P2，直到两个指针之间的子数组数字之和大于k，否则向右移动指针P1，直到两个指针之间的子数组数字之和小于k。

查找数组[5，1，4，3]中和大于或等于7的最短子数组的过程如下图所示

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    const length = nums.length;
    let ans = Infinity;
    let P1 = 0;
    let sum = 0;

    for (let P2 = 0; P2 < length; P2++ ) {
        sum += nums[P2];
        while (P1 <= P2 && sum >= target) {
            ans = Math.min(ans, P2 - P1 + 1);
            sum -= nums[P1++];
        }
    }
    return ans === Infinity ? 0 : ans;
};

复杂度分析