LeetCode_每日一题今日份_167.两数之和II-输入有序数组

秒速五厘米 2023-02-28 11:12 9阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]  
题解C\_1

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
        
        int i, j, flg = 0;
    
        for (i = 0; i < numbersSize - 1; i++){
        
            for (j = i + 1; j < numbersSize; j++){
        
                if (numbers[i] + numbers[j] == target){
        
                    flg = 1;
                    break;
                }
            }
            if (flg || numbers[i] > target)
                break;
        }
        *returnSize = 2;
        int *res = (int*)malloc(sizeof(int) * 2);
        res[0] = i + 1;
        res[1] = j + 1;
        return res;
    }

题解C\_2

/**
     * Note: The returned array must be malloced, assume caller calls free().
     */
    /*
    在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
    */
    int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
        
        int* ret = (int*)malloc(sizeof(int) * 2);
        *returnSize = 2;
    
        for (int i = 0; i < numbersSize; ++i) {
         //遍历数组
            int low = i + 1, high = numbersSize - 1;
            while (low <= high) {
        
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
        
                    ret[0] = i + 1, ret[1] = mid + 1;
                    return ret;
                } else if (numbers[mid] > target - numbers[i]) {
        
                    high = mid - 1;
                } else {
        
                    low = mid + 1;
                }
            }
        }
        ret[0] = -1, ret[1] = -1;
        return ret;
    }

模拟运行演示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230209/64bfcb53a16146b6979aac70bb0d95a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20230209/4bd8768e72f54f7c8ad8a7735c64e946.png