当前位置：首页 > article >正文

【Leetcode-两数之和】利用双指针、快排思路解决两数之和问题

article 2025/1/15 0:46:53

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个
整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] ==> 9 ，返回 [0, 1] 。

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3

输入：nums = [3,3], target = 6
输出：[0,1]

解题思路

#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return *(const int*)a - *(const int*)b;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* tempnums = (int*)malloc(sizeof(int) * numsSize);
    int* ret = (int*)malloc(sizeof(int) * 2);  // 分配返回数组：ret数组用于存储两个索引。
    int left = 0, right = numsSize - 1;
    *returnSize = 2;

    for (int i = 0; i < numsSize; ++i) { // 复制原始数组：tempnums用于存储原始数组的值，以便后续查找原始索引。
        tempnums[i] = nums[i];
    }

    qsort(nums, numsSize, sizeof(int), cmp); // 排序：对nums数组进行排序。

    int num1 = 0, num2 = 0;
    for (left = 0, right = numsSize - 1; left < right;) { // 双指针查找：使用双指针left和right查找两个数，使它们的和等于目标值target。
        int sum = nums[left] + nums[right]; // 记录匹配的数：如果找到匹配的两个数，记录它们的值num1和num2。
        if (sum == target) {
            num1 = nums[left];
            num2 = nums[right];
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    if (left >= right) { // 处理未找到匹配的情况：如果未找到匹配的两个数，释放分配的内存，设置returnSize为0，并返回NULL。
        free(tempnums);
        free(ret);
        *returnSize = 0;
        return NULL; 
    }

    int found1 = 0, found2 = 0;
    for (int i = 0; i < numsSize; ++i) { // 查找原始索引：在tempnums中查找num1和num2的原始索引，并存储到ret数组中。使用found1和found2标志确保找到两个不同的索引。
        if (!found1 && tempnums[i] == num1) {
            ret[0] = i;
            found1 = 1;
        } else if (!found2 && tempnums[i] == num2) {
            ret[1] = i;
            found2 = 1;
        }
        if (found1 && found2) break;
    }

    free(tempnums);
    return ret; // 返回结果：返回ret数组，调用者负责释放该数组。
}