培训机构网站建设要求,微信网站制作免费,武清网站建设公司,中山网站建设价位如有错误#xff0c;感谢不吝赐教、交流 文章目录 两数之和题目方法一#xff1a;暴力两重循环#xff08;不可取#xff09;方法二#xff1a;HashMap空间换时间 三数之和题目方法一#xff1a;当然是暴力破解啦方法二#xff1a;同两数之和的原理#xff0c;借助Has…如有错误感谢不吝赐教、交流 文章目录 两数之和题目方法一暴力两重循环不可取方法二HashMap空间换时间 三数之和题目方法一当然是暴力破解啦方法二同两数之和的原理借助HashMap和HashSet实现 四数之和 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
方法一暴力两重循环不可取
方法二HashMap空间换时间
借助HashMap实现如下图示例
public int[] twoSum(int[] nums, int target) {HashMapInteger, Integer map new HashMap();map.put(target - nums[0], 0);int res [] new int[2];for (int i 1; i nums.length; i) {Integer index map.get(nums[i]);if (index ! null) {res[0] (int) index;res[1] i;break;} else {map.put(target - nums[i], i);}}return res;}三数之和
题目
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 这里尤其注意一下不能包含重复的三元组借助HashSet实现比较简单不过有点费时间和空间
方法一当然是暴力破解啦
直接使用三重for循环暴力破解太费时间不可取。
方法二同两数之和的原理借助HashMap和HashSet实现
要求是三个数之和这里将其中一个数保存到HashMap中再使用双重for循环遍历即可获得三个数的答案 原理是和两数之和的原理一样。 这里需要注意会出现重复的组合结果如[0, 0,0,0]可能得组合就有[0,0,0], [0,0,0], [0,0,0] 显然这里重复了于是使用HashSet去重。
// 先对nums排序Arrays.sort(nums);HashMapInteger, Integer map new HashMap();HashSetListInteger hashSet new HashSet();map.put(-nums[0], 1);for (int i 1; i nums.length - 1; i) {for (int j i 1; j nums.length; j) {int i1 nums[i] nums[j];Integer map_val map.get(i1);if (map_val ! null) {ListInteger integers new ArrayList();integers.add(-i1);integers.add(nums[i]);integers.add(nums[j]);hashSet.add(integers);}}map.put(-nums[i], 1);}ListListInteger lists new ArrayList(hashSet);return lists;四数之和
方法原理和上面一样借助HashMap和三重for循环实现
ps:计划每日更新一篇博客今日2023-04-22日更第六天昨日更新LeetCode6_N字形变换
