数组

双指针

双指针是一种罕用的解题思路，能够应用两个相同方向或雷同方向的指针扫描数组从而达到解题目标。值得注意的是，本书在不同的章节都提到了双指针。本书中的“指针”并不专指 C 语言中的指针，而是一个绝对宽泛的概念，是能定位数据容器中某个数据的伎俩。在数组中它实际上是数字的下标。

相同指针

面试题 6：排序数组中的两个数字之和

题目：输出一个递增排序的数组和一个值 k，请问如何在数组中找出两个和为 k 的数字并返回它们的下标？假如数组中存在且只存在一对符合条件的数字，同时一个数字不能应用两次。例如，输出数组[1，2，4，6，10]，k 的值为 8，数组中的数字 2 与 6 的和为 8，它们的下标别离为 1 与 3。

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {

    let l = 0
    let r = numbers.length - 1

    while(l < r) {if(numbers[l] +numbers[r]===target) {return [l,r]
        } else if(numbers[l] +numbers[r]>target) {r--} else {l++}
    }
};

没啥好说的，相同指针的经典题目：2 数之和，显著特色有序数组。

面试题 7：数组中和为 0 的 3 个数字

题目：输出一个数组，如何找出数组中所有和为 0 的 3 个数字的三元组？须要留神的是，返回值中不得蕴含反复的三元组。例如，在数组 [-1，0，1，2，-1，-4] 中有两个三元组的和为 0，它们别离是 [-1，0，1] 和[-1，-1，2]。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {nums.sort((a, b) => a-b);
    let res = []
    for(let i = 0; i < nums.length-2;i++) {        
        // 去重
        if (i > 0 && nums[i] == nums[i - 1]) continue
        let l = i+1;
        let r = nums.length-1
        while(l < r) {
            // 怎么去重
            if(nums[l]+nums[r]+nums[i]===0) {res.push([nums[i], nums[l], nums[r]])
                while(l<r&&nums[l] === nums[++l]);
                while(l<r&&nums[r] === nums[--r]);
            } else if(nums[l]+nums[r]+nums[i]>0) {r--} else {l++}
        }
    }
    return res
};

首先是排序，难的是解决去重。

面试题 8：和大于或等于 k 的最短子数组

题目：输出一个正整数组成的数组和一个正整数 k，请问数组中和大于或等于 k 的间断子数组的最短长度是多少？如果不存在所有数字之和大于或等于 k 的子数组，则返回 0。例如，输出数组[5，1，4，3]，k 的值为 7，和大于或等于 7 的最短间断子数组是[4，3]，因而输入它的长度 2。

特色：子数组？

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let sum  = 0
    let l = 0
    let min = Infinity
    for(let r = 0; r < nums.length; r++) {sum += nums[r];
        // 满足条件，开始缩减
        while(sum>=target) {
            // 若满足缩减则减小 sun 并 挪动 l
            if(sum-nums[l]>= target) {sum-=nums[l]
                l++
            } else {
            // 若不满足则记录比拟最小值，同时跳出缩减循环
                min = Math.min(min,  r - l + 1)
                break
            }
        }
    }
    if (min===Infinity) return 0
    return min

};

快慢指针