GRD 数组刷题

1. 两数之和

var twoSum = function(nums, target) {
    const map = {}
    for(let i = 0; i< nums.length;i++) {
        if(map[nums[i]] !== undefined) return [i, map[nums[i]]] 
        let res = target - nums[i]
        map[res] = i
    }
};

121. 买卖股票的最佳时机

var maxProfit = function(prices) {
    let min = prices[0]
    let res = 0
    for(let i = 1; i<prices.length; i++) {
        min = Math.min(min, prices[i])
        res = Math.max(res, prices[i] - min)
    }
    return res
};

169. 多数元素

var majorityElement = function(nums) {
    let count = 1
    let res = nums[0]
    for(let i = 1; i < nums.length; i++) {
        if(count === 0 && res !== nums[i]) {
            res = nums[i]
        }
        res !== nums[i] ? count-- : count++
    }
    return res
};

217. 存在重复元素

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

57. 插入区间

var insert = function (intervals, newInterval) {
    let res = []
    let [nl, nr] = newInterval
    let i = 0
    while(i<intervals.length && intervals[i][1] < nl) {
        res.push(intervals[i])
        i++
    }
    while(i < intervals.length && intervals[i][0] <= nr) {
        nl = Math.min(nl, intervals[i][0])
        nr = Math.max(nr, intervals[i][1])
        i++
    }
 
    res.push([nl, nr])
    while(i<intervals.length ) {
        res.push(intervals[i])
        i++
    }
    return res
};

15. 三数之和

var threeSum = function (nums) {
    let res = []
    nums.sort((a, b) => a - b)
    let len = nums.length
 
    for (let i = 0; i < len-2; i++) {
        if(nums[i]>0) break
        if(i>0 &&nums[i] ===nums[i-1]) continue
 
        let left = i + 1, right = len - 1
 
        while (left < right) {
            let count = nums[i] + nums[left] + nums[right]
            if (count === 0) {
                res.push([nums[i], nums[left], nums[right]])
                while(left < right && nums[left] === nums[left+1]) left++
                while(left < right && nums[right] === nums[right-1]) right--
                left++
                right--
            } else if(count > 0) {
                right--
            } else {
                left++
            }
 
        }
    }
 
    return res
};

238. 除了自身以外数组的乘积

var productExceptSelf = function (nums) {
    const len = nums.length
    const res = new Array(len).fill(1)
    let left = 1
    let right = 1
    for (let i = 0; i < len; i++) {
        res[i] *= left
        left *= nums[i]
 
        res[len - 1 - i] *= right
        right *= nums[len - 1 - i]
    }
    return res
};

56. 合并区间

var merge = function(intervals) {
    intervals.sort((a, b) => a[0]-b[0])
 
    const res = [intervals[0]]
    let last = res[0]
    for(let i = 1; i< intervals.length; i++) {
        let [pl, pr] = last
        let [cl, cr] = intervals[i]
        if(pr < cl) {
            res.push([cl, cr])
            last = res[res.length - 1]
        } else if(pr < cr) {
            last[1] = cr
        }
    }
 
    return res
};

75. 颜色分类

var sortColors = function(nums) {
    let left= 0
    let right = nums.length -1
    let p1 = 0
 
    while(left<=right) {
        if(nums[left] === 0) {
            [nums[left], nums[p1]] = [nums[p1], nums[left]]
            p1++
            left++
        } else if(nums[left] === 2) {
            [nums[left],nums[right]] = [nums[right], nums[left]]
            right--
        } else {
            left++
        }
    }
};

11. 盛最多水的容器

var maxArea = function(height) {
    let max = 0
    let left = 0 
    let right = height.length - 1
 
    while(left<right) {
        max = Math.max(max, Math.min(height[left], height[right]) * (right-left))
        if(height[left] > height[right]) {
            right--
        } else {
            left++
        }
    }
    return max
};

相关笔记

• 哈希表题目（两数之和、存在重复元素）
• 双指针题目（三数之和、盛最多水的容器）
• 区间题目（合并区间、插入区间）
• 哈希表专题