JS和双索引查找

前言

在很多算法题中，要求查找一个特定的内容，可能是一个数字，也有可能是一个子串，或者是题目定义的一个满足某个性质的元素...这种题如果使用暴力搜索或者嵌套循环，往往会超时，所以我们需要一种更好的方法来降低时间复杂度：双索引技术。

起源之二分法

这种查找方法的老祖宗，就是我们高中就学习过的二分法了。当然，在大学的数据结构和算法的课程里，它的地位也非常重要，只因为它是一个O(logn)的算法。
那它的双索引是什么呢？
开始索引和结束索引。即查找范围的始索引和终索引。
上代码：

function binarySearch(arr, target) {
    var len = arr.length;
    // 在arr[l...r]之中查找target
    var l = 0,
        r = len - 1;
    while (l <= r) {
        //防止大数溢出,所以mid不是~~(l+r)/2
        var mid = l + ~~((r - l) / 2);
        if (arr[mid] == target)
            return mid;

        if (arr[mid] > target)
            r = mid - 1;
        else
            l = mid + 1;
    }

    return -1;
}

// 递归方式实现二分查找法

function __binarySearch2(arr, l,  r, target){

    if( l > r )
        return -1;

    var mid = l + ~~((r - l) / 2);
 
    if( arr[mid] === target )
        return mid;
    else if( arr[mid] > target )
        return __binarySearch2(arr, l, mid-1, target);
    else
        return __binarySearch2(arr, mid+1, r, target);

}

function binarySearch2(arr,target){
    var len = arr.length;
    return __binarySearch2( arr , 0 , len-1, target);
}

普通双索引

以leetcode第283题为例：题目要求我们把非零元素全部排列在前面，0全部放到最后。
这时我们需要两个索引：一个用来遍历数组，一个用来计算非零元素的个数。
我们设第一个指针为i，第二个指针为k，数组遍历[0...i]区间,最后得到的[0..k]区间里面全是非零元素,[k+1...i]是0

var moveZeroes = function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
         if(nums[i]){
            nums[k++] = nums[i]; 
         }
     }
     for(let i = k;i<nums.length;i++){
         nums[i] = 0;
     }
    return nums;
};

优化：交换非零元素和零元素即可

var moveZeroes = function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]) {
            //防止极端情况：全是非零
            if(i !== k)
            [nums[k], nums[i]] = [nums[i], nums[k]];
            k++;
        }
    }
    return nums;
};

对撞指针

这是双索引的一种特殊情况：即第一个索引在前，第二个索引在后，在程序运行的过程中两者不断靠近，最后达到一个临界范围，程序结束。
以leetcode的167题为例：题目要求我们找出一个数组中相加为target的两个数，并返回他们的次序。
因为输入的数组是已经排序好的，所以双索引的最初指向分别为首和尾。
我们假设两个指针为i和j,[i...j]范围内就是我们关注的，如果numbers[i]+numbers[j]等于target返回结果，小了就让i右移，大了就让j左移

var twoSum = function (numbers, target) {
    let i = 0, j = numbers.length - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] === target) return [i + 1, j + 1]
        else if (numbers[i] + numbers[j] < target) i++
        else j--
    }
    return []
};

滑动窗口

另一种双索引的特殊情况就是我们需要让两个索引保持一定的相对距离，这种做法非常类似一个滑动的窗口，在这个窗口中找到了答案就结束程序，没有找到的话就滑动之。
以leetcode的209题为例：给一个数组和一个target，找出数组中能够相加得到target的最少元素的子数组。
这个题用暴力遍历时间复杂度就是O(n^{3)，就算优化到O(n}2)还是有点让人接受不了，但是使用滑动窗口解题的话，时间复杂度就变成了O(n)
我们假设两个索引l和r,分别代表窗口的左索引和右索引，让这个窗口的数字逐个相加看是否能得到答案，并且记录长度，因为我们答案要的是元素最少的子数组。

var minSubArrayLen = function (s, nums) {
    let l = 0;
    let r = -1;//nums[l,r]为滑动窗口
    let res = nums.length + 1;
    let sum = 0;
    while (l < nums.length) {
        if (r + 1 < nums.length && sum < s) {
            r++;
            sum += nums[r];
        }
        else {
            sum -= nums[l++];
        }
        if (sum >= s) res = Math.min(res, r - l + 1);
    }
    //res没有更新,没有结果
    if (res == nums.length + 1) return 0;
    return res;
};

在滑动窗口中做记录

这是滑动窗口的加强版，就像上一道题需要记录窗口长度一样，有时候我们还需要记录其他的信息来帮助解题
以leetcode第3题为例：题目要求我们找出最长的无重复字符的子串，我们除了需要一个滑动窗口外还需要一个数据结构用来存储字符的出现次数(数组和哈希表都可以)
我们的滑动窗口每次检测到重复字符就移动，并且记录窗口长度，最后得出答案。

var lengthOfLongestSubstring = function (s) {
    let l = 0;
    let r = -1;//s[l,r]是滑动窗口
    let rst = 0;
    //其实freq的状态就是0和1
    let freq = new Array(256).fill(0);
    while (l < s.length) {
        if (r + 1 < s.length && freq[s[r + 1].charCodeAt()] === 0) {
            r++;
            freq[s[r].charCodeAt()]++;
        }
        //l和r所指的字母都一样
        else {
            freq[s[l].charCodeAt()]--;
            l++;
        }
        rst = Math.max(rst, r - l + 1);
    }
    return rst;
};