算法例子:求出数组中所有组合(两个数之和等于指定数)(Java)

您所在的位置：网站首页 › 一组等于几 › 算法例子:求出数组中所有组合(两个数之和等于指定数)(Java)

算法例子:求出数组中所有组合(两个数之和等于指定数)(Java)

2023-08-11 11:47| 来源: 网络整理| 查看: 265

这里介绍三种方法

方法1

思路: 双重for循环,每一个数和所有其他的数进行相加,如果等于目标值则打印出时间复杂度 : O(N2) 空间复杂度 : O(1)

public static void main(String[] args) { int[] nums = new int[]{1, 8, 9, 6, 4, 3, 7}; int target = 10; method1(nums, target); } public static void method1(int[] nums, int target) { for (int i = 0, size = nums.length; i if (nums[i] + nums[j] == target) { System.out.println(nums[i] + "+" + nums[j] + "=" + target); break; } } } }

结果:

1+9=10 9+1=10 6+4=10 4+6=10 3+7=10 7+3=10 方法2

思路: 1.先将数组进行排序 2.从两边进行遍历数组(left,right指针) 2.1:num[left]+num[right]=target,则打印出,则left++,right– 2.2:num[left]+num[right]target,right– 时间复杂度: 排序算法复杂度+O(N) 空间复杂度: 排序算法复杂度+O(1)

public static void main(String[] args) { int[] nums = new int[]{1, 8, 9, 6, 4, 3, 7}; int target = 10; method2(nums, target); } public static void method2(int[] nums, int target) { //1.先排序(这里使用的是快速排序){1,3,4,6,7,8,9}; quickSort(nums, 0, nums.length - 1); //2.次数num是已经排序好的数组,从两边遍历已排序的数组 for (int left = 0, right = nums.length - 1; left System.out.println(nums[left] + "+" + nums[right] + "=" + target); left++; right--; } else if (nums[left] + nums[right] //2.3.相加小于目标值,则 right-- right--; } } }

快排方法

/** * 快排 * * @param nums * @param startIndex * @param endIndex */ private static void quickSort(int[] nums, int startIndex, int endIndex) { if (startIndex int key = nums[startIndex]; while (startIndex endIndex--; } if (startIndex startIndex++; } if (startIndex int[] nums = new int[]{1, 8, 9, 6, 4, 3, 7}; int target = 10; method3(nums, target,9); } public static void method3(int[] nums, int target, int maxNum) { int[] temp = new int[maxNum]; int sub; for (int i = 0, size = nums.length; i System.out.println(sub + "+" + nums[i] + "=" + target); //然后清除此位置的数据 temp[sub - 1] = 0; } else { temp[nums[i] - 1]++; } } }

结果:

1+9=10 6+4=10 3+7=10 总结:

方法1是最先想到(时间复杂度比较大) 方法2是相对比较好的方法,(时间复杂度和空间复杂度相对比较适中)这个就得看排序算法选择的是否合适. 其他的排序算法: 冒泡排序,快速排序,堆排序箱排序,基数排序方法3是对数组的元素有一定的限制,最大值合理,是空间换时间.

如果大家有什么好的方法,希望大家可以提出来.共同学习.

【本文地址】

算法例子:求出数组中所有组合(两个数之和等于指定数)(Java)

算法例子:求出数组中所有组合(两个数之和等于指定数)(Java)

今日新闻

推荐新闻