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

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

暴力求解法：

时间复杂度：O(n^2)
空间复杂度：O(1)

    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            // - 时间复杂度：O(n^2)
            // - 空间复杂度：O(1);
            // - 暴力求解
            int[] answer = new int[2];
            for (int i = 0; i < numbers.length; i++) {
                for (int j = i + 1; j < numbers.length; j++) {
                    // - 暴力求解适用于 leetcode NO.1
                    if (numbers[i] + numbers[j] == target) {
                        answer[0] = i + 1;
                        answer[1] = j + 1;
                        break;
                    }
                }
            }
            return answer;
        }
    }

双指针求解法：

时间复杂度：O(n)
空间复杂度：O(n)

    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            // - 双指针求解
            // - 时间复杂度：O(n)
            // - 空间复杂度：O(1);
            int[] answer = new int[2];
            // - 起始下标
            int i = 0;
            // - 数组结束下标
            int j = numbers.length - 1;

            for (;;) {
                if (numbers[i] + numbers[j] == target) {
                    answer[0] = i + 1;
                    answer[1] = j + 1;
                    break;
                }
                if (numbers[i] + numbers[j] < target) {
                    i++;
                } else {
                    j--;
                }
            }

            return answer;
        }