初级算法 数组

两数之和

https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

使用 HashMap 存储整数 item 所在的 index，然后检查 map 中是否存储有 target - item 的 key 即可

const twoSum = function(nums, target) {
    const map = {};
    const result = [];
    for (let index = 0 ;index < nums.length; index++) {   
        const item = nums[index];
        const pair = target - item;
        if (map.hasOwnProperty(pair)) {
            result.push(map[pair]); // index1
            result.push(index); // index2
                return result;
        }
        map[item] = index; // index
    }
};

旋转数组

https://leetcode.cn/problems/rotate-array/

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。注意请修改原数组

PS: 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
输出: [5, 6, 7, 1, 2, 3, 4]

思路1

直接拼接数组（空间复杂度O(n)）

[1, 2, 3, 4, 5]
# 向右循环右移7位
# 等价于循环 7 % 5 = 2 位
# 截取 [0,2) [2,5)
[1, 2, 3] [4, 5]
# 拼接 [2,5) [0,2)
[4, 5, 1, 2, 3]

const rotate = function(nums, k) {
    k = k % nums.length;
    const length =  nums.length;
    const arr1 = nums.slice(0, length - k);
    const arr2 = nums.slice(length - k);
    const result = arr2.concat(arr1);
    // 逐个替换
    result.forEach((item, index)=> nums[index] = result[index])
};

思路2

翻转数组（空间复杂度O(1)）

[1, 2, 3, 4, 5]
# 1 全部翻转 [0, 5)
[5, 4, 3, 2, 1]
# 2 翻转 [0 ,2)
[4, 5, 3, 2, 1]
# 3 翻转 [2, 5)
[4, 5, 1, 2, 3]

const rotate = function(nums, k) {
    k = k % nums.length;
    const length =  nums.length;
    // 全部翻转
    nums = nums.reverse();
    // 部分翻转 前半部分 0  <==>  k - 1
    for(let i = 0; i < k / 2; i++ ){
        const temp = nums[i];
        nums[i] = nums[k - i - 1];
        nums[k - i - 1] = temp;
    }
    // 部分翻转 后半部分 k  <==> length - 1
    for(let i = k; i < (length + k - 1) / 2; i++ ){
        const temp = nums[i];
        nums[i] = nums[length + k - i - 1];
        nums[length + k - i - 1] = temp;
    }
    return nums;
};

两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

思路

直接使用 Set 即可

const intersection = (nums1, nums2) =>{
    let set1 = new Set(nums1)
    let set2 = new Set(nums2)
    const list = [...set1].filter(i => set2.has(i))
    const intersect = new Set(list);
    return [...intersect];
}

两个数组的交集 II

https://leetcode.cn/problems/intersection-of-two-arrays-ii/

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。

返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。

可以不考虑输出结果的顺序。

思路

题目有点费解，这里运行交集中出现相同的元素，相同元素的次数取两个数组中的小值，两层循环 + Map 搞定

const intersect = function(nums1, nums2) {
    // nums4 是长度较大的那个
    let nums3,nums4
    if (nums1.length < nums2.length) {
        nums3 = nums1 
        nums4 = nums2
    } else {
        nums3 = nums2
        nums4 = nums1
    }
    let countArr = [];
    nums3.forEach(item => {
        let count = 0
        for(i = 0 ;i < nums4.length; i++){
            if(nums4[i] === item) count++
        }
        countArr.push(count)
    })
    let result = [];
    const map = {};
    countArr.forEach((count,index)=>{
        let num = nums3[index]
        if(!map[num]) map[num] = 1
        map[num] += 1
        // count num 在 nums4[0, length) 中的次数
        // map[num] num 在 nums3[0, index] 中出现的次数 + 1
        // count + 1 < map[num] 说明 nums3 中次数多，不再添加
        if(count > 0 && count + 1 >= map[num]){
            result.push(num)
        }
    })
    return result
};

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

思路1

使用 hashMap

var singleNumber = function(nums) {
    // ...
};

思路2

使用逐个异或即可解决

var singleNumber = function(nums) {
    return nums.reduce((a,b) => a^b)
};

为什么，因为异或运算具有如下特性

TIP

TODO

删除排序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路1 指针比较

使用两个指针，右指针始终往右移动，

• 如果右指针指向的值等于左指针指向的值，左指针不动。
• 如果右指针指向的值不等于左指针指向的值，那么左指针往右移一步，然后再把右指针指向的值赋给左指针。

/**
 * @param {number[]} nums
 * @return {number}
 */
const removeDuplicates = function(nums) {
    if(nums.length === 1) return 1;
    let left = 0;
    let right = 1;
    while(right < nums.length){
        if(nums[left] === nums[right]){
            right += 1;
        } else {
            left += 1;
            nums[left] = nums[right];
            right += 1;
        }
    }
    const length = left + 1;
    nums.length = length;
    return length
};

买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

买卖股票的最佳时机 II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

买卖股票的最佳时机 III

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/