16. 最接近的三数之和

相对于暴力解法，双指针能够通过首尾指针和合理移动，减少不合理情况的遍历，即a+b+c < target，则c向左移动，a+b+c > target，b向右移动

进一步可以总结出：若想要使两数之和逼近某一个目标值，可使用双指针对已排序数组进行查找

对已排序数组的遍历时跳过重复值的通用优化：

1
2
3
int p0 = p + 1;
while(nums[p0] == nums[p] && p0 < q)
    p0++;
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
int threeSumClosest(vector<int>& nums, int target) {
    int ans = 1e7;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int sum;
    auto update = [&](int cur)
    {
        if(abs(cur - target) < abs(ans - target))
        {
            ans = cur;
        }
    };
    for(int i = 0; i < n - 2; i++)
    {
        if(i > 0 && nums[i] == nums[i-1])
            continue;
        int p = i + 1;
        int q = n - 1;
        while(p < q)
        {
            sum = nums[i] + nums[p] + nums[q];
            if(sum == target)
            {
                return target;
            }
            update(sum);
            if(sum < target)
            {
                int p0 = p + 1;
                while(nums[p0] == nums[p] && p0 < q)
                    p0++;
                p = p0;
            }
            if(sum > target)
            {
                int q0 = q - 1;
                while(q0 > p && nums[q0] == nums[q])
                {
                    q0--;
                }
                q = q0;
            }

        }
    }
    return ans;
}

19. 删除链表的倒数第N个节点

怎样一次遍历找到倒数第N个节点？

双指针，前面的指针在后面的指针前N+1的位置，同步前进，然后当前面的指针指到nullptr时，后面的指针处于倒数N+1位置，这时令：

1
p->next = p->next->next;
怎样保证最后返回正确的头节点？（原链表的头节点可能被删除）

开始时在head前new一个节点hair：

1
ListNode* hair = new ListNode(0, head); // (val, next)

最后返回hair->next

18. 四数之和

先将数组用sort()进行排序

双重循环遍历前两个数，后两个数分配双指针一前一后

外面双重循环：

1
2
3
4
5
6
7
for(int i = 0; i < n-3; i++)
{
	for(int j = i+1; j < n-2; j++)
	{
		......
	}
}

双指针起始位置：

1
2
int p = j + 1;
int q = n - 1;

剪枝操作：

在外层的两重循环中分别做如下几种情况的剪枝：

当前值nums[i]与上一个值nums[i-1]相同时，continue

当前值nums[i]加上后面连续三个数nums[i+1], nums[i+2], nums[i+3]的和大于target，则之后不论如何取值都一定大于target，直接跳出循环break

当前值nums[i]加上倒数三个最大的值nums[n-1], nums[n-2], nums[n-3]的和小于target，说明以nums[i]起始的任意四个数的和均小于target，跳出本次循环continue

对于第二层循环做类似的三种情况的剪枝处理

415. 字符串相加

实现两个字符串的数值相加，不能用类型转换

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
string addStrings(string num1, string num2) {
    //双指针，双指针的“指针”不一定非得是指针类型，能做flag标记就行
	int i = num1.length() - 1;
	int j = num2.length() - 1;
	string res;
	int multi = 1;
    //进位
	int add = 0;
	while (i >= 0 || j >= 0 || add > 0)
	{
		int x = 0;
		int y = 0;
		if (i >= 0)
		{
            //两者相减得到的是int型
			x = num1[i] - '0';
		}
		if (j >= 0)
		{
			y = num2[j] - '0';
		}
		int result = x + y + add;
		res.push_back('0' + result % 10);
		add = result / 10;
		i--;
		j--;
	}
    //因为每次push_back是从低位到高位的，所以结果要翻转
	reverse(res.begin(), res.end());
	return res;
}

75. 颜色分类

数组中只有0，1，2三种值，对其排序的方式：

双指针p0和p2，p0用于交换0，p2用于交换2

p0 = 0，p2 = n - 1

一次遍历，当前值如果为0，交换当前位置和p0位置的值，当前值如果为2，和p2交换

1
2
3
4
5
6
7
8
9
10
11
// 这里while的使用要注意，对照输入[2,1,2]
while(i <= p2 && nums[i] == 2)
{
    swap(nums[i], nums[p2]);
    --p2;
}
if(nums[i] == 0)
{
    swap(nums[i], nums[p0]);
    ++p0;
}