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

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;
}