leetcode-Array

一、模板

1. 移动/删除(双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 注意 len，i 的取值
/**
 * 覆盖
 */

let len = 0 // 指向下一个需要被覆盖的位置
for(let i = 0;i < nums.length;i++)
  if(nums[i] !== 0)
    nums[len++] = nums[i]

/**
 * 交换
 */

let len = 0 // 指向下一个需要被覆盖的位置
for(let i = 0;i < nums.length;i++)
  if(nums[i] !== 0)
    if(i !== len){
      swap(nums,i,len)
			len++
    }else
      len++

2. 搜索（对撞指针/二分）

  • 二分查找
  • 对撞指针

3. 反转/回文串（对撞指针）

  • 对撞指针
1
2
let l = 0, r = nums.length-1
while(l < r){...}

4. 子数组/子串（滑动窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 重复的字符，用freq = [] 记录频数
// [l ... r]窗口
 let l = 0, r = -1
 let sum = 0
 while (l < nums.length) {
   if ( r + 1 < nums.length && sum < s) {
     ++ r
     sum += nums[r]
   } else {
     sum -= nums[l]
     l++
   } 
	 // 获得一个窗口后，处理 [l ... r] 窗口
 }

二、题目

(1) 移动/删除(双指针)

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 暴力
 */

var moveZeroes = function(nums) {
  const arr = []
  for(let i = 0;i < nums.length;i++){
    if(nums[i] !== 0)
      arr.push(nums[i])
  }
  for(let i = 0;i < arr.length;i++)
    nums[i] = arr[i]
  
  for(let i = arr.length;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] !== 0)
      nums[k++] = nums[i]
      
  for(let i = k;i < nums.length;i++)
    nums[i] = 0
  
  return nums
};


/**
 * 交换
 */
  
var moveZeroes = function (nums) {
  let len = 0
  for (let i = 0; i < nums.length; i++)
    if (nums[i] !== 0) {
      if (len !== i) {
        swap(nums, i, len)
        len++
      } else {
        len++
      }
    }

  return nums;
};

27. 移除元素

1
2
3
4
5
6
7
var removeElement = function(nums, val) {
  let len = 0
  for(let num of nums)
    if(num !== val)
      nums[len++] = num
  return len
};

26. 删除排序数组中的重复项

1
2
3
4
5
6
7
var removeDuplicates = function(nums) {
  let len = 0
  for(let num of nums)
    if(num !== nums[len])
      nums[++len] = num
  return len + 1
};

80. 删除排序数组中的重复项 II

1
2
3
4
5
6
7
8
9
var removeDuplicates = function (nums) {
  if(nums.length <= 2) return nums.length
  let len = 2
  for (let i = 2; i < nums.length; i++)
    if (nums[i] != nums[len - 2])
      nums[len++] = nums[i]

  return len
}

(2) 双指针(对撞指针)

167. 两数之和 II - 输入有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 暴力
 */

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

/**
 * 二分 O(nlogn)
 */

var twoSum = function(numbers, target) {
  for(let i = 0;i < numbers.length-1;i++){
    let t = target - numbers[i]
    let l = i+1, r = numbers.length-1
    while(l <= r){
      let mid = l + ((r-l) >> 1)
      if(numbers[mid] === t)
        return [i + 1, mid + 1]
      else if(numbers[mid] < t)
        l = mid+1
      else 
        r = mid-1
    }
  }
};

/**
 * 对撞指针 O(n)
 */

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

15. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 排序+对撞指针
 */

var threeSum = function (nums) {
  let res = []
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break
    if (i > 0 && nums[i] === nums[i - 1]) continue

    let l = i + 1, r = nums.length - 1
    while (l < r) {
      let result = nums[l] + nums[r] + nums[i]

      if (result === 0) {
        res.push([nums[i], nums[l], nums[r]])
        l++
        r--
        while(l<r && nums[l] === nums[l-1]) l++
        while(l<r && nums[r] === nums[r+1]) r--
      }
      else if (result < 0)
        l++
      else
        r--
    }
  }
  return res
};

125. 验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 对撞指针
 */

var isPalindrome = function (s) {
  s = s.replace(/[\W|_]/g, "").toLowerCase()
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l] !== s[r]) return false
    l++
    r--
  }
  return true
};

/**
 * 对撞指针
 */

var isPalindrome = function (s) {
  let l = 0, r = s.length - 1
  while (l < r) {
    if (/\W|_/.test(s[l]) && ++l) continue
    if (/\W|_/.test(s[r]) && r--) continue
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
}

344. 反转字符串

1
2
3
4
5
6
7
8
9
10
var reverseString = function(s) {
  let l = 0,r = s.length-1
  while(l < r){
    const temp = s[l]
    s[l] = s[r]
    s[r] = temp 
    l++
    r--
  }
};

345. 反转字符串中的元音字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var reverseVowels = function (s) {
  let w = ['a', 'e', 'i', 'o', 'u']
  let arr = s.split("")
  let i = 0, j = arr.length - 1
  while (i < j) {
    if (!w.includes(arr[i].toLowerCase()) && ++i) continue
    if (!w.includes(arr[j].toLowerCase()) && j--) continue
    if (arr[i] !== arr[j]) {
      const temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
    i++
    j--
  }
  return arr.join("")
};

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
var maxArea = function (height) {
  let max = 0
  let i = 0, j = height.length - 1
  while (i < j) {
    max = height[i] < height[j] 
    ? Math.max(max,(j-i)*height[i++])
    : Math.max(max,(j-i)*height[j--])
  }
  return max
};

(3) 子数组/子串（滑动窗口）

209. 长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 滑动窗口
 */

var minSubArrayLen = function (s, nums) {
  let l = 0, r = -1
  let sum = 0
  let res = nums.length + 1

  while (l < nums.length) {
    if ( r+1 < nums.length && sum < s) {
      ++ r
      sum += nums[r]
    } else {
      sum -= nums[l]
      l++
    }

    if(sum >= s)
      res = Math.min(res,r-l+1)
  }

  if(res === nums.length+1) return 0
    
  return res
};


/**
 * 滑动窗口
 */

var minSubArrayLen = function (s, nums) {
  let l = 0
  let len = 0
  let sum = 0
  for(let r = 0;r < nums.length;r++){
    sum += nums[r]
    while(sum >= s){
      len = len === 0 ? r-l+1 : Math.min(len,r-l+1)
      sum-=nums[l++]
    }
  }
  return len
};

3. 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 滑动窗口
 */

var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) return s.length

  let freq = new Array(256).fill(0)
  let l = 0,r=-1
  let res = 0
  
  while(l < s.length){
    if( r+1 < s.length && freq[s[r+1].charCodeAt()]===0){
      r++
      freq[s[r].charCodeAt()]++
    }else{
      freq[s[l].charCodeAt()]--
      l++
    }

    res = Math.max(res,r-l+1)
  }
  
  return res
};

var lengthOfLongestSubstring = function (s) {
  let l = 0,
    res = 0,
    map = new Map()

  for (let r = 0; r < s.length; r++) {
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1
    }
    
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }

  return res
};

438. 找到字符串中所有字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 滑动窗口
 */

var findAnagrams = function (s, p) {
  if (s.length < p.length) return []
  let freq_s = new Array(26).fill(0)
  let freq_p = new Array(26).fill(0)
  let l = 0, r = -1, res = []

  for (let i = 0; i < p.length; i++) {
    freq_p[p[i].charCodeAt() - 97]++;
    freq_s[s[++r].charCodeAt() - 97]++;
  }
  if (isAnagrams(freq_s, freq_p))
    res.push(l);

  while (r < s.length - 1) {
    freq_s[s[++r].charCodeAt() - 97]++;
    freq_s[s[l++].charCodeAt() - 97]--;

    if (isAnagrams(freq_s, freq_p))
      res.push(l);
  }

  return res;

  function isAnagrams(arr_s, arr_p) {
    for (let i = 0; i < arr_p.length; i++)
      if (arr_s[i] !== arr_p[i]) return false
    return true
  }
}