用javascript分类刷leetcode19.数组(图文视频讲解)5

var twoSum = function (numbers, target) {
    let len = numbers.length,
        left = 0,
        right = len - 1,
        mid = 0
    for (let i = 0; i < len; ++i) {//循环数组，从右边的元素二分查找另一个元素
        left = i + 1
        while (left <= right) {
            mid = parseInt((right - left) / 2) + left
            if (numbers[mid] == target - numbers[i]) {
                return [i + 1, mid + 1]
            } else if (numbers[mid] > target - numbers[i]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
    }
    return [-1, -1]
}

var twoSum = function (numbers, target) {
    let [left, right] = [0, numbers.length - 1];//左右指针
    while (left < right) {//
        if (numbers[left] + numbers[right] > target) {//和大了 right左移一位
            right--;
        } else if (numbers[left] + numbers[right] < target) {//和小了left右移一位
            left++;
        } else {
            return [left + 1, right + 1];
        }
    }
};

var intersection = function (nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);//数组转成set
    if (set1.size > set2.size) {//用size小的数组遍历
        [set1, set2] = [set2, set1]
    }
    const intersection = new Set();
    for (const num of set1) {//遍历set1
        if (set2.has(num)) {//元素如果不存在于set2中就加入intersection
            intersection.add(num);
        }
    }
    return [...intersection];//转成数组
};

// nums1 = [4,5,9]
// nums2 = [4,4,8,9,9]
// intersection = [4,9]
var intersection = function (nums1, nums2) {
    nums1.sort((x, y) => x - y);//排序
    nums2.sort((x, y) => x - y);
    const length1 = nums1.length,
        length2 = nums2.length;
    let index1 = 0,//双指针
        index2 = 0;
    const intersection = [];
    while (index1 < length1 && index2 < length2) {//双指针遍历数组
        const num1 = nums1[index1],
            num2 = nums2[index2];
        if (num1 === num2) {//如果两个指针指向的元素相等 就时其中一个交集
            //防止重复加入
            if (num1 !== intersection[intersection.length - 1]) {
                intersection.push(num1);
            }
            index1++;
            index2++;
        } else if (num1 < num2) {
            index1++;//num1 < num2说明mums1需要向右移动
        } else {
            index2++;//num1 > num2说明mums1需要向左移动
        }
    }
    return intersection;
};

var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);//排序
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] === nums[i + 1]) {//判断相邻元素是否相同
            return true;
        }
    }
    return false;
};

var containsDuplicate = function(nums) {
    const set = new Set();
    for (const x of nums) {
        if (set.has(x)) {
            return true;
        }
        set.add(x);
    }
    return false;
};

var sortArrayByParity = function(A) {
    return A.sort((a, b) => (a & 1) - (b & 1))
};

var sortArrayByParity = function(A, l = 0, r = A.length - 1) {
    while(l !== r) {
        while (r > 0 && A[r] & 1) r--
        while (l < r && (A[l] & 1) === 0) l++
        [A[l], A[r]] = [A[r], A[l]]
    }
    return A
};

var sortColors = function (nums) {
    let p0 = 0 //指向0
    let p1 = 0 //指向0

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {//如果当前i指向的元素等于1，则交换当前元素和p1指向的元素
            let temp = nums[p1]
            nums[p1] = nums[i]
            nums[i] = temp
            p1++
        } else if (nums[i] === 0) {//如果当前i指向的元素等于0，则交换当前元素和p0指向的元素
            let temp = nums[p0]
            nums[p0] = nums[i]
            nums[i] = temp
            //如果p0小于p1 则此时p0指向的元素是1，与i位置元素交换之后 这个交换过去的1位置就不对了 所以交换过去的1需要在和p1交换一下
            if (p0 < p1) {
                temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
            }
            //每次交换0之后都要移动p0和p1，如果p0===p1，则前面都是0，如果p0<p1,前面的代码已经交换了两次
            p0++
            p1++
        }
    }
};

var sortColors = function (nums) {
    let p0 = 0;//指向0
    let p2 = nums.length - 1;//指向2
    for (let i = 0; i <= p2; i++) {//当循环到了p2 说明p2右边的元素都是正确的数，所以i<=p2
        //如果此时i指向元素2 i小于p2 则不断交换p2和i指向的元素 因为交换过来的数可能还是2，那这个2就处于不正确的位置了
        while (nums[i] === 2 && i < p2) {
            let temp = nums[i];
            nums[i] = nums[p2];
            nums[p2] = temp;
            p2--;
        }
        //如果此时i指向元素0 则交换p0和i指向的元素
        if (nums[i] === 0) {
            let temp = nums[i];
            nums[i] = nums[p0];
            nums[p0] = temp;
            p0++;
        }
    }
};

//写法2
var sortColors = function (nums) {
    const swap = (list, p1, p2) => [list[p1], list[p2]] = [list[p2], list[p1]]
    let red = 0,
        blue = nums.length - 1,
        p = 0

    while (p <= blue) {
        switch (nums[p]) {
            case 0:
                swap(nums, red++, p)
                p++
                break;
            case 1://遇见1 一直让p++ 这样即使交换过来的是2 也是处于正确的位置
                p++
                break;
            case 2:
                swap(nums, blue--, p)

                break;
            default:
                break;
        }
    }
};

var moveZeroes = function (nums) {
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {//遇到非0元素，让nums[j] = nums[i]，然后j++
            nums[j] = nums[i];
            j++;
        }
    }
    for (let i = j; i < nums.length; i++) {//剩下的元素全是0
        nums[i] = 0;
    }
    return nums;
};

var moveZeroes = function(nums) {
    let left=0,right=0
    while(right<nums.length){
        if(nums[right]!==0){//遇上非0元素，交换left和right对应的元素
            swap(nums,left,right)
            left++//交换之后left++
        }
        right++
    }
};
function swap(nums,l,r){
    let temp=nums[r]
    nums[r]=nums[l]
    nums[l]=temp
}

const intersect = (nums1, nums2) => {
    const map = {};
    const res = [];
    if (nums1.length < nums2.length) {
        [nums1, nums2] = [nums2, nums1]
    }
    for (const num1 of nums1) {//nums1中各个元素的频次
        if (map[num1]) {
            map[num1]++;
        } else {
            map[num1] = 1;
        }
    }
    for (const num2 of nums2) { //遍历nums2
        const val = map[num2];
        if (val > 0) {            //在nums1中
            res.push(num2);         //加入res数组
            map[num2]--;            //匹配掉一个，就减一个
        }
    }
    return res;
};

const intersect = (nums1, nums2) => {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b); //排序两个数组
    const res = [];
    let p1 = 0;//指向nums1中的元素
    let p2 = 0;//指向nums2中的元素
    while (p1 < nums1.length && p2 < nums2.length) {//不越界条件
        if (nums1[p1] > nums2[p2]) {//p1指向的元素大，移动p2
            p2++;
        } else if (nums1[p1] < nums2[p2]) {//p2指向的元素大，移动p1
            p1++;
        } else {
            //遇到相同则加入入res，移动两指针
            res.push(nums1[p1]);
            p1++;
            p2++;
        }
    }
    return res;
};

var productExceptSelf = function (nums) {
    const res = [];
    res[0] = 1;
      //从左往右遍历
      //记录从左到当前位置前一位的乘积
    for (let i = 1; i < nums.length; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }

    let right = 1;
      //从右往左遍历
      //从左到当前位置前一位的乘积 乘上 右边元素的积
    for (let j = nums.length - 1; j >= 0; j--) {
        res[j] *= right;
        right *= nums[j];
    }

    return res;
};

var minSubArrayLen = function(target, nums) {
    const len = nums.length;
    let l = r = sum = 0, 
        res = len + 1; //最大的窗口不会超过自身长度
    while(r < len) {
        sum += nums[r++];//扩大窗口
        while(sum >= target) {
            res = res < r - l ? res : r - l;//更新最小值
            sum-=nums[l++];//缩小窗口
        }
    }
    return res > len ? 0 : res;
};

const swap = (nums, i, j) => {
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
};
var sortArrayByParityII = function(nums) {
    const n  = nums.length;
    let j = 1;
    for (let i = 0; i < n; i += 2) {
        if (nums[i] & 1) {//循环偶数位置 如果遇到了奇数
            while (nums[j] & 1) {//循环奇数位置 如果遇到了第一个偶数
                j += 2;
            }
            swap(nums, i, j);//交位置换
        }
    }   
    return nums;
};