数组

主要是双指针

二分查找法

LeetCode 704

遵循原则：左闭右开（推荐） | 左闭右闭 | 左开 可以但不推荐

[left, right] | [left, right) | (left, right] | (left, right)

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
left = 0
right = num.size - 1	// 左闭右开的时候，因为 右开 ，所以不需要 -1
// num = [1,1]
// 这里面填什么符号，应当先考虑遵循上面的什么原则
// 如果是左闭右闭 [left, right], 考虑 left == right 区间是否合法成立, 成立就可以填'='号
// 同理如果是左闭右开 [left, right), left == right 时 区间不合法，所以不可以填'='号
while(left __ right){
    middle = (left+right)/2	// 这里需要考虑是否会溢出越界
    
    // target在middle的左边，需要更新 左区间的右边界 right
    if(nums[middle] > target){
        // 这里同样需要考虑遵循什么原则
        right = middle - 1  // 左闭右闭的话, 当前循环已经考虑过了nums[middle]这个位置了, 所以在下一次循环的时候就不再需要考虑nums[middle], 直接从middle的前一位开始考虑
    	right = middle 		// 左闭右开的话, 当前循环还未考虑nums[middle]这个位置了, 所以在下一次循环的时候需要考虑nums[middle]
    }
    
    // target在middle的右边，需要更新 右区间的左边界 left
    else if(nums[middle] < target){
        left = middle + 1	// 因为都是左闭, 所以middle位置当前循环已经考虑过了, 所以从下一位开始考虑
    }
    
    else
        return middle
    
}
return -1

移除元素

LeetCode 27

提要：删除数组中的指定元素，实际上是覆盖操作！

双指针思路，一个快指针，一个慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * parme arr: T[]		[1,2,3,4,3,5]
 * parme target: T		3
 */
slow = 0		// 需要覆盖的位置下标
fast = 0		// 

for(let i = 0; i < arr.length; i++){
    if(arr[slow] != target){		// 如果当前下标的值 不是目标值，就直接 覆盖更新
        arr[slow++] = arr[fast]		// 之后慢指针前移
    }
    // 如果当前下标的值 是目标值，就表示 这个值 不需要 覆盖更新到数组中
    // 之后快指针前移，慢指针则不移动，等待下一个不是target的值 覆盖到慢指针指向的地方
}

return slow;	// 最后slow所指向的下标，正好就是新数组的长度

有序数组的平方

LeetCode 977

思路一：数组每个数都先平方，然后在排序，时间复杂度 O(nlogn) ，空间复杂度 O(1)

思路二：双指针，因为最大平方后最大的元素位于数组两端，时间复杂度 O(n)，空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * parme nums: number[]			// [-5,-3,-1,1,2,4,6]
 */

i = 0
j = nums.length - 1
result = Array(nums.length)		k = nums.length - 1		// 从后往前赋值

// i 和 j 相等时，需要处理最后一个元素
while(i<=j){
    if(nums[i]² < nums[j]²){
        result[k--] = nums[j--]²	// 后面比前面大，就把后面的平方赋值到新数组中
    }
    else{
        result[k--] = nums[i++]²	// 前面比后面大，就把前面的平方赋值到新数组中
    }
}
return result;

长度最小的子数组（滑动窗口）

LeetCode 209

双指针：滑动窗口

简单来说就是：

​ 小了 前面的往前移动 扩大窗口；

​ 大了 后面的往前移动 缩小窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * parme nums: number[]		// [1,3,4,5,6,8,9,13,14,20]
 * parme targe: number		// 14
 */

i = 0			// 滑动窗口前面
k = 0			// 滑动窗口后面
result = Max	// 子数组的元素和===target，子数组的最小长度
count = 0
for(i = 0; i < nums.length; i++){
    count += nums[i]
    while(count >= target){
        result = Min(result, i - k + 1)		// i-k+1: 滑动窗口的长度
        
        count = count - nums[k++]	// 后面的往前缩小窗口，并且减去缩小后 窗口外的那个元素的值
    }
}
return resule;

螺旋矩阵

LeetCode 59

遵循原则：左闭右开

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
/**
 * parme n	// n 维矩阵
 */

坐标：(x,y)
count = 1		// 用来赋值用的

startX = 0
startY = 0
offset = 1		// 可以理解为，这一行/列 最后 少处理 几个元素 (左闭右开的基础上 每转一圈少一个元素)

k = n / 2 		// 圈数
while(k--){
    // 上边
    for(x = startX, y = startY; y < n - offset; y++){
        nums[x][y] = count++
    }
    // 右边
    for(; x < n - offset; x++){	// 注意：此时的 y 已经移动到最后一列了，只需要将 x 向下移就可以
        nums[x][y] = count++
    }
    // 底边
    for(; y > startY; y--){		// 注意：此时的 x 已经移动到最后一行了，只需要将 y 向前移就可以
        nums[x][y] = count++
    }
    // 左边
    for(; x > startX; x--){		// 注意：此时的 y 已经移动到第一列了，只需要将 x 向上移就可以
        nums[x][y] = count++
    }
    
    // 此时遍历完第一圈了, 需要往里面缩小一圈
    startX++;		startY++;		offset++;
    
    // 但其实这里可以发现 StartX === StartY === offset - 1
}

// 最后如果这是个 基数 的 二维数组
// 转完圈之后会剩下最中间的一个格子，此时单独赋值即可
if(n % 2){
    nums[x][y] = count		// while 循环最后的自增 会把下标指向最后中间的格子
}
return nums