【牛客-程序员代码面试指南】不重复打印排序数组中相加和为给定值的所有二元组
2022/2/13 17:17:17
本文主要是介绍【牛客-程序员代码面试指南】不重复打印排序数组中相加和为给定值的所有二元组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述
给定排序数组arr和整数k,不重复打印arr中所有相加和为k的不降序二元组
例如, arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9], k = 10,打印结果为:
1, 9
2, 8
[要求]
时间复杂度为O(n)O(n),空间复杂度为O(1)O(1)
输入描述:
第一行有两个整数n, k
接下来一行有n个整数表示数组内的元素
输出描述:
输出若干行,每行两个整数表示答案
按二元组从小到大的顺序输出(二元组大小比较方式为每个依次比较二元组内每个数)
示例
输入:
10 10
-8 -4 -3 0 1 2 4 5 8 9
复制
输出:
1 9
2 8
题解
双指针,注意跳过重复值
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] t1 = br.readLine().split(" "); int k = Integer.valueOf(t1[1]); String[] t2 = br.readLine().split(" "); int[] arr = new int[t2.length]; for (int i = 0; i < t2.length; i++) { arr[i] = Integer.valueOf(t2[i]); } ArrayList<List<Integer>> ans = new ArrayList<>(); int s = 0, e = arr.length - 1; while (s < e) { if (arr[s] + arr[e] == k) { List<Integer> m = new ArrayList<>(); m.add(arr[s]); m.add(arr[e]); ans.add(m); // 需要跳过重复值 while (s < e && arr[s] == arr[s + 1]) { s++; } while (s < e && arr[e - 1] == arr[e]) { e--; } s++; e--; } else if (arr[s] + arr[e] < k) { s++; } else { e--; } } for (List<Integer> i : ans) { System.out.println(i.get(0) + " " + i.get(1)); } } }
这篇关于【牛客-程序员代码面试指南】不重复打印排序数组中相加和为给定值的所有二元组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南