leetcode 22-03-29

发表于 更新于 分类于 阅读次数： 本文字数： 450 阅读时长 ≈ 2 分钟

今日份 leetcode

  • 217. 存在重复元素
  • 167. 两数之和 II - 输入有序数组

217. 存在重复元素

提交时才发现这道题之前做过一次，但好像没发题解

解题思路

先将代码进行排序，然后逐一比较，若当前元素等于后一个，则表示存在重复元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C
int cmp(int *x, int *y) {
    return *x - *y;
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// javascript
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for(let i = 0; i < nums.length; i++)
    {
        if(nums[i] == nums[i + 1])
        return true
    }
    return false
};

167. 两数之和 II - 输入有序数组

解题思路

因为给定的数组是有序的，所以可以得出以下结论
左边和右边相加，如果比目标值大，说明右边的数太大了，所以往前推
左边和右边相加，如果比目标值小，说明左边的数太小了，所以往后推
左边和右边相加，如果等于目标值，说明找到了，所以返回下标 +1，一开始没看清楚题目以为是返回下标

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int * res = (int *) malloc (sizeof(int) * 2);
    int left = 0, right = numbersSize - 1;
    while(left < numbersSize){
        if(numbers[left] + numbers[right] == target){
            res[0] = left + 1;
            res[1] = right + 1;
            *returnSize = 2;
            return res;
        }
        if(numbers[left] + numbers[right] > target) right--;
        if(numbers[left] + numbers[right] < target) left++;
    }
    *returnSize = 0;
    return NULL;
}

最后吐槽一下，为什么别人暴力能过，我暴力超时😭
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int * res = (int *) malloc (sizeof(int) * 2);
    for(int i = 0; i < numbersSize - 1; i++){
        for(int j = i + 1; j < numbersSize; j++){
            if(numbers[i] + numbers[j] == target){
                res[0] = i + 1;
                res[1] = j + 1;
                *returnSize = 2;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}