给一个升序数组,找出两个数字相加等于 target 的个数。
程序员文章站
2024-02-04 08:18:10
...
int[] nums = {1,2,2,3,3,3,3,4,4,5,5} target = 6 res = 12
public int twoSum(int[] nums, int target) {
int n = nums.length;
if (n <= 0) return 0;
int count = 0;
for (int lo = 0, hi = n-1; lo < hi;) {
if (nums[lo] + nums[hi] < target) lo++;
else if (nums[lo] + nums[hi] > target) hi--;
else {
if (nums[lo] != nums[hi]) {
int count1 = 0;
int tmp1 = nums[lo];
while (nums[lo] == tmp1) {
count1++;
lo++;
}
int count2 = 0;
int tmp2 = nums[hi];
while (nums[hi] == tmp2) {
count2++;
hi--;
}
count += count1 * count2;
} else {
int count1 = 0;
int tmp = nums[lo];
while (nums[lo] == tmp) {
count1++;
lo++;
}
count += count1 * (count1 - 1) / 2; // count1 取两个 C n 2
}
}
}
return count;
}
如果数组是无序的
public int twoSum(int[] nums, int target) {
int n = nums.length;
if (n <= 0) return 0;
HashMap<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int i = 0; i < n; i++) {
if (map.containsKey(target-nums[i])) {
count += map.get(target - nums[i]);
}
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
}
else {
map.put(nums[i], 1);
}
}
return count;
}
推荐阅读
-
给一个升序数组,找出两个数字相加等于 target 的个数。
-
快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的值
-
个有序的整形数组,给定一个数,在数组中找出两个数的和等于这个数,并打印其下标
-
一个整形数组,给定一个数,在数组中找出两个数的和等于这个数
-
go语言实现--找出一个数组中的两个数,这两个数之和等于一个给定的值
-
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的 任意个数之和 等于 target,并打印出所有结果的索引。
-
快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的值
-
一个数组nums,其中任意两个值等于给定值target,返回这两个值在nums里的位置
-
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
-
一个数组nums,其中任意两个值等于给定值target,返回这两个值在nums里的位置