数组

双指针

双指针是一种罕用的解题思路，能够应用两个相同方向或雷同方向的指针扫描数组从而达到解题目标。值得注意的是，本书在不同的章节都提到了双指针。本书中的“指针”并不专指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

};

快慢指针