FilesExpand file tree

 master

/

TwoSumIIInputArrayIsSorted167.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (53 loc) · 1.97 KB

 master

/

TwoSumIIInputArrayIsSorted167.java

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (53 loc) · 1.97 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

/**

* Given an array of integers that is already sorted in ascending order, find

* two numbers such that they add up to a specific target number.

*

* The function twoSum should return indices of the two numbers such that they

* add up to the target, where index1 must be less than index2.

*

* Note:

* Your returned answers (both index1 and index2) are not zero-based.

* You may assume that each input would have exactly one solution and you may

* not use the same element twice.

*

* Example:

* Input: numbers = [2,7,11,15], target = 9

* Output: [1,2]

* Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

*/

public class TwoSumIIInputArrayIsSorted167 {

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

if (numbers == null || numbers.length < 2) return new int[2];

int len = numbers.length;

for (int i=0; i<=len-2; i++) {

int idx = binarySearch(numbers, target-numbers[i], i+1, len-1);

if (idx != -1) {

return new int[]{i+1, idx+1};

}

}

return new int[2];

}

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

if (l > r) return -1;

if (l == r) return numbers[l] == target ? l : -1;

int mid = (l + r) / 2;

if (numbers[mid] == target) return mid;

if (numbers[mid] > target) {

return binarySearch(numbers, target, l, mid-1);

} else {

return binarySearch(numbers, target, mid+1, r);

}

}

// using Arrays.binarySearch

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

if (numbers == null || numbers.length < 2) return new int[2];

int len = numbers.length;

for (int i=0; i<=len-2; i++) {

int idx = Arrays.binarySearch(numbers, i+1, len, target - numbers[i]);

if (idx >= 0) {

return new int[]{i+1, idx+1};

}

}

return new int[2];

}

}