leecode两数之和多种求解

港控/mmm° 2022-08-31 16:18 143阅读 0赞

题目：

> 给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
> 
> 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <=  
> answer\[0\] < answer\[1\] <= numbers.length 。
> 
> 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

方法一：  
使用暴力求解

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int element;
            int[] a = new int[2];
            for (int i = 0; i < numbers.length; i++) { 
                element = target - numbers[i];
                for (int j = 0; j < numbers.length; j++) { 
                    if(i!=j&&element == numbers[j]){ 
                        a[1] = i+1;
                        a[0] = j+1;
                        break;
                    }
                }
            }
            /*for (int i : a) { System.out.println("i:::"+i); }*/
            return a;
        }
    }

方法二：  
如果题目中为提供一个有序数组，那么可以使用二分查找  
确定一个数，另一个数靠二分查找搜索

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            for (int i = 0; i < numbers.length; ++i) { 
                int low = i + 1, high = numbers.length - 1;
                while (low <= high) { 
                    int mid = (high - low) / 2 + low;
                    if (numbers[mid] == target - numbers[i]) { 
                        return new int[]{ i + 1, mid + 1};
                    } else if (numbers[mid] > target - numbers[i]) { 
                        high = mid - 1;
                    } else { 
                        low = mid + 1;
                    }
                }
            }
            return new int[]{ -1, -1};
        }
    }

方法三：双指针  
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 \\text\{numbers\}\[i\]+\\text\{numbers\}\[j\]=\\text\{target\}numbers\[i\]+numbers\[j\]=target 是唯一解，其中 0 \\leq i<j \\leq \\text\{numbers.length\}-10≤i<j≤numbers.length−1。初始时两个指针分别指向下标 00 和下标 \\text\{numbers.length\}-1numbers.length−1，左指针指向的下标小于或等于 ii，右指针指向的下标大于或等于 jj。除非初始时左指针和右指针已经位于下标 ii 和 jj，否则一定是左指针先到达下标 ii 的位置或者右指针先到达下标 jj 的位置。

如果左指针先到达下标 ii 的位置，此时右指针还在下标 jj 的右侧，\\text\{sum\}>\\text\{target\}sum>target，因此一定是右指针左移，左指针不可能移到 ii 的右侧。

如果右指针先到达下标 jj 的位置，此时左指针还在下标 ii 的左侧，\\text\{sum\}<\\text\{target\}sum<target，因此一定是左指针右移，右指针不可能移到 jj 的左侧。

由此可见，在整个移动过程中，左指针不可能移到 ii 的右侧，右指针不可能移到 jj 的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int low = 0, high = numbers.length - 1;
            while (low < high) { 
                int sum = numbers[low] + numbers[high];
                if (sum == target) { 
                    return new int[]{ low + 1, high + 1};
                } else if (sum < target) { 
                    ++low;
                } else { 
                    --high;
                }
            }
            return new int[]{ -1, -1};
        }
    }