通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。
双指针的典型场景
(1)从两端向中间迭代数组。
(2)一个指针从头部开始，而另一个指针从尾部开始。
c
void swap(char *a, char *b) {
char t = *a;
*a = *b, *b = t;
}
void reverseString(char *s, int sSize) {
for (int left = 0, right = sSize - 1; left < right; ++left, --right) {
swap(s + left, s + right);
}
}
c++
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
for (int left = 0, right = n - 1; left < right; ++left, --right) {
swap(s[left], s[right]);
}
}
};
C
int cmp(int *a, int *b) {
return *a - *b;
}
int arrayPairSum(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int ans = 0;
for (int i = 0; i < numsSize; i += 2) {
ans += nums[i];
}
return ans;
}
解析：
1.qsort函数
qsort是C语言标准库中用于对数组进行快速排序的函数。它的函数原型如下：
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
qsort函数的第一个参数是需要排序的数组的指针base，第二个参数是数组的元素个数nitems，第三个参数是每个元素的大小size（以字节为单位），第四个参数是一个指向比较函数的指针compar。
比较函数compar接受两个指向待比较元素的指针，并返回一个整数值，表示它们的大小关系。如果第一个元素小于第二个元素，则返回一个负数；如果它们相等，则返回0；如果第一个元素大于第二个元素，则返回一个正数。这个函数的原型如下：
int (*compar)(const void *, const void*)
C++
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < nums.size(); i += 2) {
ans += nums[i];
}
return ans;
}
};
c
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
for (int i = 0; i < numbersSize; ++i) {
int low = i + 1, high = numbersSize - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
ret[0] = i + 1, ret[1] = mid + 1;
return ret;
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
ret[0] = -1, ret[1] = -1;
return ret;
}
解释:
函数 twoSum 接受四个参数：
numbers：一个指向整数数组开头的指针
numbersSize：表示 numbers 数组的大小的整数
target：目标整数
returnSize：一个指向整数的指针，用于返回结果数组的大小
c++
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
for (int i = 0; i < numbers.size(); ++i) {
int low = i + 1, high = numbers.size() - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return {i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return {-1, -1};
}
};
c
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
int low = 0, high = numbersSize - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
ret[0] = low + 1, ret[1] = high + 1;
return ret;
} else if (sum < target) {
++low;
} else {
--high;
}
}
ret[0] = -1, ret[1] = -1;
return ret;
}
c++
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int low = 0, high = numbers.size() - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return {low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return {-1, -1};
}
};
c
int removeElement(int* nums, int numsSize, int val) {
int left = 0;
for (int right = 0; right < numsSize; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
c++
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
};
c
int removeElement(int* nums, int numsSize, int val) {
int left = 0, right = numsSize;
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
c++
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};
c
int findMaxConsecutiveOnes(int* nums, int numsSize) {
int maxCount = 0, count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) {
count++;
} else {
maxCount = fmax(maxCount, count);
count = 0;
}
}
maxCount = fmax(maxCount, count);
return maxCount;
}
c++
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int maxCount = 0, count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
count++;
} else {
maxCount = max(maxCount, count);
count = 0;
}
}
maxCount = max(maxCount, count);
return maxCount;
}
};
c
int minSubArrayLen(int s, int* nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < numsSize; i++) {
int sum = 0;
for (int j = i; j < numsSize; j++) {
sum += nums[j];
if (sum >= s) {
ans = fmin(ans, j - i + 1);
break;
}
}
}
return ans == INT_MAX ? 0 : ans;
}
C++
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= s) {
ans = min(ans, j - i + 1);
break;
}
}
}
return ans == INT_MAX ? 0 : ans;
}
};
c
int lower_bound(int *a, int l, int r, int q) {
if (a[r] < q) return -1;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= q) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
int minSubArrayLen(int s, int *nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
int ans = INT_MAX;
int *sums = (int *)malloc(sizeof(int) * (numsSize + 1));
// 为了方便计算，令 size = n + 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
for (int i = 1; i <= numsSize; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= numsSize; i++) {
int target = s + sums[i - 1];
int bound = lower_bound(sums, 1, numsSize, target);
if (bound != -1) {
ans = fmin(ans, bound - (i - 1));
}
}
return ans == INT_MAX ? 0 : ans;
}
C++
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
vector<int> sums(n + 1, 0);
// 为了方便计算，令 size = n + 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
auto bound = lower_bound(sums.begin(), sums.end(), target);
if (bound != sums.end()) {
ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
}
}
return ans == INT_MAX ? 0 : ans;
}
};
c
int minSubArrayLen(int s, int *nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < numsSize) {
sum += nums[end];
while (sum >= s) {
ans = fmin(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
C++
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
};