双指针法
双指针法常用于求和和排序之类的场景,是一种时间换空间的算法。
学习算法只看理论知识是远远不够的，需要从各种各样的题中去细细体悟算法的魅力，从而真真的把知识刻在脑子里，成为自己的一部分；
所以此篇文章基本都是算法题，让我们从实际的代码角度来揭开双指针的神秘面纱吧！
下面的题都是从某一方面的知识写的例子，大家如果有其他想法，代码敲起来~
1. 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。
这道题没有用到双指针，单纯的用来练练手，从第二题开始为双指针算法题；
示例: 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
求和问题基本可以反向思考为 差值问题，比如说a + b = target,则可以想成target - a = b, 这样就能避免对数组进行两次循环，再对循环的值相加；
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
|
let nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function demo (nums, target) {
const diffs = {}
const len = nums.length
for (var i = 0; i < len; i++) {
if (diffs[target - nums[i]] !== undefined) {
return [diffs[target - nums[i]], i]
}
diffs[nums[i]] = i
}
};
const result = demo(nums, 16);
console.log(result);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
function demo(nums, target) {
const len = nums.length;
for (var i = 0; i < len; i++) {
let num = target - nums[i];
let index = nums.indexOf(num);
if (index !== -1) {
return [i, index];
}
}
}
const result2 = demo(nums, 16);
console.log(result2);
|
2. 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
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
|
function demo(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1
while(i >= 0 && j >= 0) {
if(nums1[i] >= nums2[j]) {
nums1[k] = nums1[i]
i--
k--
} else {
nums1[k] = nums2[j]
j--
k--
}
}
while(j>=0) {
nums1[k] = nums2[j]
k--
j--
}
};
|
投机写法
1
2
3
4
5
| function demo(nums1, m, nums2, n) {
nums1.splice(m);
nums2.splice(n);
return [...nums1, ...nums2].sort((a, b) => a - b);
}
|
3. 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: [ 0, 1, 0, 3, 12 ], 输出: [ 1, 3, 12, 0, 0 ], 只能在当前数组上操作，不能使用新建数组、合并等方法；
常规方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| let arr = [0, 1, 0, 3, 12];
function demo(arr) {
let num = arr.length;
if(!num) return;
for (var i = 0; i <= num; i++) {
if (arr[i] === 0) {
arr.splice(i, 1);
arr.push(0);
i--;
num--;
}
}
}
demo(arr);
console.log(arr);
|
双指针方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| let arr = [0, 1, 0, 3, 12];
function demo(nums) {
let n = nums.length;
if (!n) return;
let i = 0;
for (var j = 0; j < n; j++) {
if (nums[j] !== 0) {
nums[i] = nums[j];
i++;
}
}
for (var k = i; k < n; k++) {
nums[k] = 0
}
return nums;
};
console.log(demo(arr));
|
4. 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
注意：答案中不可以包含重复的三元组。
解析:
1.在数组和求和的算法中，我们要习惯性在脑子里显现求和就是求差值、 指针 这两思路！
2.尽量从求差值的角度去减少循环次数，从而降低时间复杂度；
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
let nums = [-3, 3, 1, -1, -2, 0, -1, 1 - 2, 2];
let m = 0;
function demo(arr, m) {
if (!arr || !arr.length) return;
let result = [];
arr = arr.sort((a, b) => a - b);
let len = arr.length;
for (var i = 0; i < len; i++) {
let j = i + 1;
let k = len - 1;
if (arr[i] === arr[i - 1]) {
continue;
}
while (j < k) {
if ((arr[i] + arr[j] + arr[k]) > m) {
k--;
if (arr[k] === arr[k + 1]) {
k--;
}
}
if ((arr[i] + arr[j] + arr[k]) < m) {
j++;
if (arr[j] === arr[j - 1]) {
j++;
}
}
if ((arr[i] + arr[j] + arr[k]) === m) {
result.push([arr[i], arr[j], arr[k]]);
k--;
j++;
if (arr[k] === arr[k + 1]) {
k--;
}
if (arr[j] === arr[j - 1]) {
j++;
}
}
}
}
return result;
}
console.log(demo(nums, m));
|
