Two Sum - Difference equals to target
程序员文章站
2024-03-08 11:51:46
...
Given an array of integers, find two numbers that their difference
equals
to a target value.
where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.
Notice
It's guaranteed there is only one available solution
Example
Given nums = [2, 7, 15, 24]
, target = 5
return [1, 2]
(7 - 2 = 5)
该题目可以使用hashmap的方式尽心处理,也可以使用双指针的方式进行处理。使用双指针的方法需要重新设置一个类,进而定义一个带有索引和
该处数值的一个类。
java
class Pair {
int value;
int index;
public Pair(int value, int index) {
this.value = value;
this.index = index;
}
}
public class Solution {
/*
* @param nums: an array of Integer
* @param target: an integer
* @return: [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum7(int[] nums, int target) {
// write your code here
if (nums == null || nums.length < 2) {
return new int[]{};
}
target = Math.abs(target);
Pair[] p = new Pair[nums.length];
for (int i = 0; i < nums.length; i++) {
p[i] = new Pair(nums[i], i);
}
Comparator<Pair> cmp = new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.value - b.value;
}
};
Arrays.sort(p, cmp);
int left = 0, right = 0, sum = 0;
int[] arr = new int[2];
while (left < nums.length && right < nums.length) {
sum = p[right].value - p[left].value;
if (sum == target) {
if (left == right) {
right++;
continue;
}
arr[0] = p[left].index + 1;
arr[1] = p[right].index + 1;
break;
} else if (sum < target) {
right++;
} else {
left++;
}
}
Arrays.sort(arr);
return arr;
}
}
推荐阅读
-
【Lintcode】533. Two Sum - Closest to target
-
Two Sum - Difference equals to target
-
Two Sum - Greater than target
-
Two Sum - Less than or equal to target
-
【Lintcode】443. Two Sum - Greater than target
-
【Lintcode】609. Two Sum - Less than or equal to target
-
Two Sum - Closest to target
-
Two Sum - Greater Than Target
-
Two Sum - Less than or equal to target