【算法集训】基础算法：双指针

344. 反转字符串

// 双指针思路
void reverseString(char* s, int sSize) {int i = 0,j = sSize - 1;while(i < j) {char tmp = s[i];s[i] = s[j];s[j] = tmp;i ++, j --;}
}

392. 判断子序列

// 双指针
bool isSubsequence(char* s, char* t) {// 定义s和t的下标指针int i = 0, j = 0;while( s[i] && t[j] ) {if( s[i] == t[j] ) {i++;}j++;}return s[i] == '\0';
}

1. 两数之和

int cmp(const void * p1, const void * p2) {return (*(int *) p1) - (*(int *) p2);
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int save[10010];memcpy(save, nums, sizeof(int) * numsSize); //保存数组qsort(nums, numsSize, sizeof(int), cmp); //排序// 双指针比较,得出符合条件的数int i = 0, j = numsSize - 1;while(i < j) {int sum = nums[i] + nums[j];if(sum > target) {j--;}else if(sum < target) {i++;}else {break;}}int * ret = (int *)malloc(sizeof(int) * 2);// 如果找不到则返回空if(i > j) {*returnSize = 0;return ret;}// 找出当前的数在原数组中的下标值for(int a = 0; a < numsSize; ++a) {if(save[a] == nums[i]) {i = a;break;}}for(int b = 0; b < numsSize; ++b) {if(save[b] == nums[j] && b != i) {j = b;break;}}// 将i和j的顺序排序if(j > i) {int t = i;i = j;j = t;}*returnSize = 2;ret[0] = i;ret[1] = j;return ret;
}