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

leetcode1.两数之和

article 2024/9/24 13:25:32

题目描述

给定一个整数数组 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]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

解题思路

方法一：双指针

int cmp(const void *a,const void *b){
    return (*(int*)a)-(*(int*)b);
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* res = (int*)malloc(2 * sizeof(int));
    if (nums == NULL || numsSize == 0) {
        return res;
    }
    int *copy=(int*)malloc(numsSize* sizeof(int));
     for(int i=0;i<numsSize;i++){
        copy[i]=nums[i];
     }
      qsort(copy,numsSize,sizeof(int),cmp);
    int left=0,right=numsSize-1;
    while(left<right){
        int sum=copy[left]+copy[right];
        if(sum==target){
           for(int i=0;i<numsSize;i++){
                if(nums[i]==copy[left]){
                    res[0]=i;
                    break;
                }
            }
            for(int i=0;i<numsSize;i++){
                if(nums[i]==copy[right]&&i!=res[0]){
                    res[1]=i;
                    break;
                }
            }
             *returnSize = 2;
             return res;
            
        }
        else if(sum>target)
        right--;
        else{
           left++;
        }
    }
    *returnSize = 0;
    return NULL;
}

```c
int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);

    if (returnSize == 2) {
        printf("Indices: %d, %d\n", result[0], result[1]);
    } else {
        printf("No two sum solution\n");
    }

    free(result);
    return 0;
}

方法二：哈希表

#define size 10000
#define mid 5000
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* res = (int*)malloc(2 * sizeof(int));
     *returnSize=2;
    if (nums == NULL || numsSize == 0) {
        return res;
    }
    int* hash=(int*)calloc(size,sizeof(int));
    memset(hash,-1,size*sizeof(int));
    for(int i=0;i<numsSize;i++){
        int other=target-nums[i];
        if(hash[other+mid]!=-1){
            res[0]=hash[other+mid];
            res[1]=i;
       
        return res;
        }
        hash[nums[i]+mid]=i;
    }
    *returnSize=0;
    return NULL;
}