LeetCode 双指针章节

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

有两种情况，是快乐数，不断计算能得到1；不是快乐数，不断计算会遇到之前出现过的数，会无限循环。当结果为1时计算一直得到的也是1，与这题141. 环形链表类似；采取快慢指针，用数作指针即可，判断相遇时是否为一。

int getHappyNum(int n) {
    int ret = 0;
    while (n) {
        int x = n % 10;
        ret += x * x;
        n /= 10;
    }
    return ret;
}
bool isHappy(int n) {
    int slow = n, fast = getHappyNum(n);
    while (slow != fast) {
        slow = getHappyNum(slow);
        fast = getHappyNum(getHappyNum(fast));
    }
    return slow == 1;
}

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

**进阶：**你能尽量减少完成的操作次数吗？

通过双指针仅维护一个非零数组 (0, left)。

void moveZeroes(vector<int>& nums) {
    // 双指针确定非零数组，再将零元素数组全部置零
    int left = 0, right = 0;
    while (right < nums.size()) {
        if (nums[right] != 0)
            nums[left++] = nums[right];
        right++;
    }
    while (left < nums.size()) {
        nums[left++] = 0;
    }
}

双指针可以用来数组分块，用来维护非零(0, left)和零(left, right)两个数组，将上面算法进行优化得到：

void moveZeroes(vector<int>& nums) {
    // 双指针将数组分块，划分为非零数组和零数组
    int left = 0, right = 0;
    while (right < nums.size()) {
        if (nums[right] != 0)
            swap(nums[left++], nums[right]);
        right++;
    }
}

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

这题虽然是一道简单题但并不简单。可以自己画图模拟一下从前往后和从后往前。如果再创建一个新的数组，遍历原数组，更新新数组即可，但这样不符合题意。如果从前往后就地在数组上修改会发现产生了覆盖肯定不对。所以考虑从后往前地构造，需要先找到最后一个开始的位置。

void duplicateZeros(vector<int>& arr) {
    int begin = 0, count = 0;
    while (count < arr.size()) {
        if (arr[begin] == 0) 
            count += 2;
        else
            count++;
        begin++;
    }
    begin--;
	
    // 最后一个数是零，复写后会超出原数组
    int dest = arr.size() - 1;
    if (count > arr.size()) {
        begin--;
        arr[dest--] = 0;
    }

    while (begin >= 0) {
        arr[dest--] = arr[begin];
        if (arr[begin] == 0) 
            arr[dest--] = 0;
        begin--;
    }
}

对上面代码还可以进行简单优化，可以发现找从后往前构造的开始位置的count就是构建数组的dest。通过双指针寻找cur，再通过双指针复写零。

void duplicateZeros(vector<int>& arr) {
    int cur = 0, dest = -1;
    while (cur < arr.size()) {
        if (arr[cur] == 0)
            dest += 2;
        else
            dest++;
        if (dest >= arr.size() - 1)
            break;
        cur++;
    }
    if (dest == arr.size()) {
        arr[dest - 1] = 0;
        dest -= 2;
        cur--;
    }
    while (cur >= 0) {
        arr[dest--] = arr[cur];
        if (arr[cur] == 0)
            arr[dest--] = 0;
        cur--;
    }
}

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

这题就是排好序的[1. 两数之和](https://leetcode.cn/problems/two-sum/)，利用双指针算法即可。

vector<int> twoSum(vector<int>& price, int target) {
    int left = 0, right = price.size() - 1;
    while (left < right) {
        int sum = price[left] + price[right];
        if (sum > target)
            right--;
        else if (sum < target)
            left++;
        else
            return {price[left], price[right]};
    }
    return {};
}

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

双指针为数组两个端点，不断计算区间的容量取最大值。采用贪心的思想将缩小区间，如果每次更新容器的最小的

边，确保较大的一边不变，容量的最大值不会错过。

int maxArea(vector<int>& height) {
    int ans = 0;
    int left = 0, right = height.size() - 1;
    while (left < right) {
        ans = max(ans, (right - left) * min(height[right], height[left]));
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return ans;
}

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 10^5

与1. 两数之和类似，只需要确定一个值为target，找到两数之和为target的相反数即可。

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    for (int i = 0; i < nums.size() - 2; ++i) {
        // 去重
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        int target = -nums[i];
        // 只统计nums[i] < 0的情况即可
        if (target < 0)
            break;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                ans.push_back({nums[i], nums[left++], nums[right--]});
                // 去重left，right
                while (left < nums.size() - 1 && nums[left] == nums[left - 1])
                    left++;
                while (right > 0 && nums[right] == nums[right + 1])
                    right--;
            }
        }
    }
    return ans;
}

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

与15. 三数之和类似，只需要确定两个数nums[i]和num[j]，再通过两数之和确定四数之和即可nums[i] + nums[j] + nums[left] + nums[right] == target。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    if (nums.size() < 4)
        return {};
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    for (int i = 0; i < nums.size() - 3; ++i) {
        // 去重
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        for (int j = i + 1; j < nums.size() - 2; ++j) {
            // 去重
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                // 数据会溢出，采用long long
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    ans.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                    // 去重left，right
                    while (left < nums.size() - 1 && nums[left] == nums[left - 1])
                        left++;
                    while (right > 0 && nums[right] == nums[right + 1])
                        right--;
                }
            }
        }
    }
    return ans;
}

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

遍历数组，保持[0, left - 1]全为0，[right + 1, nums.size() - 1]全为2，最后[left, right]就全为1了。当i > right，就完成了数组划分，不用再继续遍历了。三种情况，对应操作：

• nums[i] == 0时，交换nums[left]与当前值并i++。
• nums[i] == 1时，i++即可。
• nums[i] == 2时，交换nums[left]，但不能i++，还要对交换得到值再进行判断。

void sortColors(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int i = 0;
    while (i <= right) {
        if (nums[i] == 0)
            swap(nums[left++], nums[i++]);
        else if (nums[i] == 1)
            i++;
        else // nums[i] == 2
            swap(nums[right--], nums[i]);
    }
}

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

在有序区间，先确定最大值，判断剩下区间与最大值可构成的三角形数量。有两种情况：

• nums[right] + nums[left] > nums[i]时，left向左移动一定也可以构成三角形，可以构成right - left个三角形。
• nums[right] + nums[left] < nums[i]时，left向左移动才能构成三角形。

以此作为循环，不断从后往前枚举最大值+双指针判断即可。

int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    for (int i = nums.size() - 1; i >= 1; --i) {
        int left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                ans += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    return ans;
}

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

使用两个指针 l 和 r 分别指向数组的起始和结束位置，同时使用 l_max 和 r_max 分别记录左侧和右侧的最大高度。在每次循环中，更新 l_max 和 r_max，比较左右高度：

• 如果 height[l] < height[r]，说明当前位置的雨水量由左侧的最大高度决定，因此计算 l_max - height[l] 并累加到结果中，然后将左指针 l 右移一位。
• 否则，说明当前位置的雨水量由右侧的最大高度决定，因此计算 r_max - height[r] 并累加到结果中，然后将右指针 r 左移一位。

int trap(vector<int>& height) {
    int ans = 0;
    int l = 0, r = height.size() - 1;
    int l_max = 0, r_max = 0;

    while (l < r) {
        l_max = max(height[l], l_max);
        r_max = max(height[r], r_max);

        if (height[l] < height[r]) {
            ans += l_max - height[l];
            l++;
        } else {
            ans += r_max - height[r];
            r--;
        }
    }
    return ans;
}

，比较左右高度：

• 如果 height[l] < height[r]，说明当前位置的雨水量由左侧的最大高度决定，因此计算 l_max - height[l] 并累加到结果中，然后将左指针 l 右移一位。
• 否则，说明当前位置的雨水量由右侧的最大高度决定，因此计算 r_max - height[r] 并累加到结果中，然后将右指针 r 左移一位。

int trap(vector<int>& height) {
    int ans = 0;
    int l = 0, r = height.size() - 1;
    int l_max = 0, r_max = 0;

    while (l < r) {
        l_max = max(height[l], l_max);
        r_max = max(height[r], r_max);

        if (height[l] < height[r]) {
            ans += l_max - height[l];
            l++;
        } else {
            ans += r_max - height[r];
            r--;
        }
    }
    return ans;
}