package LeetCode;

public class LeetCode167 {

//https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

/**

* 暴力解法

*

* @param numbers

* @param target

* @return

*/

// 时间复杂度: O(n^2)

// 空间复杂度: O(1)

public int[] twoSum(int[] numbers, int target) {

if (numbers.length < 2 /*|| !isSorted(numbers)*/)

throw new IllegalArgumentException("Illegal argument numbers");

for (int i = 0; i < numbers.length; i++)

for (int j = i + 1; j < numbers.length; j++)

if (numbers[i] + numbers[j] == target) {

int[] res = {i + 1, j + 1};

return res;

}

throw new IllegalStateException("The input has no solution");

}

// 二分搜索法

// 时间复杂度: O(nlogn)

// 空间复杂度: O(1)

public int[] twoSum2(int[] numbers, int target) {

if (numbers.length < 2 /*|| !isSorted(numbers)*/)

throw new IllegalArgumentException("Illegal argument numbers");

for (int i = 0; i < numbers.length - 1; i++) {

int j = binarySearch(numbers, i + 1, numbers.length - 1, target - numbers[i]);

if (j != -1) {

// 返回的数从1开始，所以下面都+1了

int[] res = {i + 1, j + 1};

return res;

}

}

throw new IllegalStateException("The input has no solution");

}

private int binarySearch(int[] nums, int l, int r, int target) {

if (l < 0 || l > nums.length)

throw new IllegalArgumentException("l is out of bound");

if (r < 0 || r > nums.length)

throw new IllegalArgumentException("r is out of bound");

while (l <= r) {

int mid = l + (r - l) / 2;

if (nums[mid] == target)

return mid;

if (target > nums[mid])

l = mid + 1;

else

r = mid - 1;

}

return -1;

}

// 对撞指针

// 时间复杂度: O(n)

// 空间复杂度: O(1)

public int[] twoSum3(int[] numbers, int target) {

if (numbers.length < 2 /*|| !isSorted(numbers)*/)

throw new IllegalArgumentException("Illegal argument numbers");

int l = 0, r = numbers.length - 1;

while (l < r) {

if (numbers[l] + numbers[r] == target) {

int[] res = {l + 1, r + 1};

return res;

} else if (numbers[l] + numbers[r] < target)

l++;

else // numbers[l] + numbers[r] > target

r--;

}

throw new IllegalStateException("The input has no solution");

}

}