算法（十四）数组之双指针

两数之和 II - 输入有序数组(leetcode_167)

题目

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0]

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]


题解

首尾双指针解决问题，示例代码如下所示：

class Solution {
public:
vector twoSum(vector& numbers, int target) {
int length = numbers.size();
int low = 0;
int high = length - 1;
while (low if (numbers[low] + numbers[high] > target) {--high;
} else {++low;
}
}
if (low == high) {
return vector();
} else {
return {low + 1, high + 1};
}
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]


题解

类似two_sum的解决方法，思路如下：

1. 升序排序。
2. 遍历一个元素时，寻找该元素与其后的两个元素组成的三个元素是否和为0。
3. 遍历过程中注意重复问题。

示例代码如下：

class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
if (nums.empty()) {
return result;
}
int length = nums.size();
sort(nums.begin(), nums.end()); // 排序是核心
for (int k = 0; k if (nums[k] > 0) {break;
}
// nums[k] == nums[k - 1]很重要，如果判断条件为nums[k] == nums[k + 1]，则会导致误跳过的情况，bad case为[-1, -1, 2, 4]
if (k > 0 && nums[k] == nums[k - 1]) {continue;
}
int i = k + 1;
int j = length - 1;
int target = -nums[k];
while (i ({nums[k], nums[i], nums[j]})); while (i }
}
return result;
}
};


复杂度

时间：O(N^2) -> 两层遍历
空间：常量?

题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。


题解

解题思路和<3sum>几乎是一模一样的，示例代码如下所示：

class Solution {
public:
void update(int cur) {
if (abs(cur - target_inner) best = cur;
}
}
int threeSumClosest(vector& nums, int target) {
target_inner = target;
int length = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i if (i > 0 && nums[i] == nums[i - 1]) {continue;
}
int left = i + 1;
int right = length - 1;
while (left target) { // 这时需要令right向左移动 while (left }
}
return best;
}
private:
double best = 1e7;
int target_inner = 0;
};


复杂度

时间：O(N^2) -> 两层遍历
空间：O(logN) -> 快速排序的空间复杂度

题目

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

题解

双指针解决问题，l从左向右，r从右向左，遍历过程中计算当前最大的面积，并且如果height[l] = height[r]，则height[r]成为短板，因而需要–r来打破这一短板。示例代码如下：

class Solution {
public:
int maxArea(vector& height) {
int l = 0;
int r = height.size() - 1;
int result = -1;
while (l int cur_area = min(height[l], height[r]) * (r - l);
result = max(result, cur_area);
if (height[l] } else {--r;
}
}
return result;
}
};


复杂度

时间：O(N)
空间：O(1)

题目

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

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]


题解

双指针left和right解决问题，当没有0时left和right一起移动；当有0时left不动，right动；当right遇到非0时，置换right和left然后left和right一起动。示例代码如下所示：

class Solution {
public:
void moveZeroes(vector& nums) {
if (nums.empty()) {
return;
}
int length = nums.size();
int left = 0;
int right = 0;
while (right if (nums[right]) {swap(nums[right], nums[left++]);
}
++right;
}
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

题解

遇到相同元素直接跳过，遇到不相同元素扔到前面，示例代码如下所示：

class Solution {
public:
int removeDuplicates(vector& nums) {
int length = nums.size();
if (length == 0) {
return 0;
}
int i = 0;
for (int j = 1; j if (nums[j] != nums[i]) {nums[++i] = nums[j];
}
}
return i + 1;
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

题解

快慢指针解决问题。慢指针slow记录目标数组长度，fast记录已经检查过的数组长度，示例代码如下所示：

class Solution {
public:
int removeDuplicates(vector& nums) {
int length = nums.size();
if (length <= 2) {
return length;
}
int slow = 2;
int fast = 2;
while (fast if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow;
}
++fast;
}
return slow;
}
};


复杂度

时间：O(n)
空间：O(1)

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

题解

与<删除有序数组中的重复项>思路大体类似，但不同点在于如果nums[j]不等于val时，直接用nums[j]替换nums[i](而不是nums[i+1])，示例代码如下所示：

class Solution {
public:
int removeElement(vector& nums, int val) {
int length = nums.size();
if (length == 0) {
return 0;
}
int i = 0;
for (int j = 0; j if (nums[j] != val) {nums[i] = nums[j];++i;
}
}
return i;
}
};

复杂度

时间：O(N)
空间：O(1)

题目

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

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

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]


题解1

两遍遍历数组解决问题。第一遍把0换到前面来，第二遍把1换到所有0的后面，示例代码如下所示：

public:
void sortColors(vector& nums) {
int length = nums.size();
if (length == 0) {
return;
}
int ptr = 0;
for (int i = 0; i if (nums[i] == 0) {swap(nums[i], nums[ptr++]);
}
}
for (int i = ptr; i if (nums[i] == 1) {swap(nums[i], nums[ptr++]);
}
}
}
}


题解2

双指针遍历一遍数组解决问题。p0指针指向0区域的下一个元素，p1指针指向1区域的下一个元素。求解过程见这里，示例代码如下所示：

class Solution {
public:
void sortColors(vector& nums) {
int length = nums.size();
if (length == 0) {
return;
}

int p0 = 0;
int p1 = 0;
for (int i = 0; i if (nums[i] == 1) {swap(nums[i], nums[p1++]);
} else if (nums[i] == 0) {swap(nums[i], nums[p0]);if (p0 }
}
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000


题解

合并两个有序思路，记录第mid个元素，如果两个元素的长度和为偶数，需要特殊处理。

class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int left_ptr = 0;
int right_ptr = 0;
int length1 = nums1.size();
int length2 = nums2.size();
int length = length1 + length2;
int mid = length / 2;
double result;
int count = 0;
while (left_ptr int left_value = left_ptr int right_value = right_ptr int tmp_result = left_value <= right_value ? left_value : right_value;
if (left_value <= right_value) {++left_ptr;
} else {++right_ptr;
}
if (length % 2 == 1) {if (count == mid) { result = tmp_result; break;}
} else if (count == mid - 1) {result = tmp_result; // 中位数左边的数
} else if (count == mid) {result = (double)(result + tmp_result) / 2.0; // 中位数右边的数break;
}
++count;
}

return result;
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]


题解

利用数组已经有序的条件，完成一遍遍历解决问题，不用重新排序，示例代码如下所示：

class Solution {
public:
vector sortedSquares(vector& nums) {
int length = nums.size();
vector ans(length, 0);
for (int i = 0, j = length - 1, pos = length - 1; i <= j;) {
int square_i = nums[i] * nums[i];
int square_j = nums[j] * nums[j];
if (square_i > square_j) {ans[pos] = square_i;++i;
} else {ans[pos] = square_j;--j;
}
--pos;
}
return ans;
}
};


复杂度

时间：O(N)
空间：O(1)

题目

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。

示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。


题解

i遍历所有的偶数位置元素，j遍历所有奇数位置元素，如果在i遍历过程中出现奇数，则令j找到一个偶数和i位置的元素互换即可完成目标，示例代码如下所示：

class Solution {
public:
vector sortArrayByParityII(vector& nums) {
int length = nums.size();
int j = 1;
for (int i = 0; i if (nums[i] % 2 == 1) {while (nums[j] % 2 == 1) { j += 2;}swap(nums[i], nums[j]);
}
}
return nums;
}
};

和为s的连续正数序列(剑指offer_57)

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]


题解

正常遍历解决方案，示例代码如下

class Solution {
public:
vector> findContinuousSequence(int target) {
vector> result;
if (target <= 0) {
return result;
}
int low = 1;
int high = 2;
while (low int cur_sum = (low + high) * (high - low + 1) / 2;
if (cur_sum > target) {++low;
} else if (cur_sum == target) {vector tmp_result;for (int i = low; i <= high; ++i) { tmp_result.emplace_back(i);}result.emplace_back(tmp_result);++low; // 这里++high和++low效果是一样的
} else {++high;
}
}
return result;
}
};

调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。


题解

双指针解决问题，示例代码如下所示：

class Solution {
public:
vector exchange(vector& nums) {
int length = nums.size();
if (length == 0) {
return vector();
}
int begin = 0;
int end = length - 1;
while (begin if (nums[begin] % 2 == 1) {++begin;continue;
}
if (nums[end] % 2 == 0) {--end;continue;
}
swap(nums[begin++], nums[end--]);
}
return nums;
}
};