当前位置: 首页 > 面试题库 >

手写代码:数组的2-sum,3-sum,问题(leetcode原题)

伊俊能
2023-03-14
本文向大家介绍手写代码:数组的2-sum,3-sum,问题(leetcode原题)相关面试题,主要包含被问及手写代码:数组的2-sum,3-sum,问题(leetcode原题)时的应答技巧和注意事项,需要的朋友参考一下

参考回答:

2SUM问题

最常见的是2SUM问题(1. 2SUM),就是数组中找出两个数相加和为给定的数。 这道题有两种思路:

  1. 一种思路从首尾搜索两个数的和,并逐步逼近。
  2. 另外一种思路是固定一个数A,看SUM-A是否在这个数组之中。

对于第一种思路如下:

此方法是先将数组从小到大排序 设置两个指针,一个指向数组开头,一个指向数组结尾,从两边往中间走。直到扫到满足题意的为止或者两个指针相遇为止。 此时这种搜索方法就是类似于杨氏矩阵的搜索方法,就是从杨氏矩阵的左下角开始搜索,直到找到为止。 如果此时题目条件变为如果没有找出最接近的2SUM和问题,解决方法跟上面是一样的 用这种方法2SUM问题的时间复杂度是O(nlogn)O(nlog⁡n)的,主要在于排序的时间。

第二种思路方法如下:

对数组中的每个数建立一个map/hash_map 然后再扫一遍这个数组,判断target-nums[i]是否存在,如果存在则说明有,不存在继续找。当然这样做的话,需要处理一个细节:判重的问题。 代码如下【注意因为题目中说一定有解所以才下面这样写,如果不一定有解,则还要再加一些判断】

vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,vector<int>> mark;
for(int i=0;i<nums.size();i++)
mark[nums[i]].push_back(i);
for(int i = 0;i<nums.size();i++){
if(target-nums[i] == nums[i]){
if(mark[nums[i]].size() > 1){
vector<int> tmp{i,mark[nums[i]][1]};
return tmp;
}
}else{
if(mark.find(target-nums[i]) != mark.end()){
vector<int> tmp{i,mark[target-nums[i]][0]};
return tmp;
}
}
}
}

 

3-SUM 问题

Question: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.The solution set must not contain duplicate triplets.

根据给定的容量为 n 的整数数组,找到所有满足 a + b + c = 0 的三个元素a、b 、c组合,需去重;

解法

修改问题为:满足 a + b + c = target,target是给定数,原题即 target = 0;

根据题目可知,与 2-SUM 问题类似,在整数数组中不放回的取出三个元素,其和等于给定数(0),不同的是,满足条件的解有多个而且需要去重;

首先想到的解法是,遍历数组,然后调用 2-SUM 问题中的方法寻找两个元素相加等于当前元素的补足,最后执行去重操作;这样的话,查询的时间复杂度是$O(n^2)$,空间复杂度是$O(n^2)$,去重的时间复杂度是$O(n^2)$,空间复杂度是$O(1)$,这绝对不能算一个好方案;

思考其他思路,既然要去重,可以先对数组执行一次排序,这样的话在遍历的时候可以跳过相同元素;在确定一个当前元素后,找另外两个元素相加作为当前元素的补足,此时的解可能是多个的,采用首尾标记的方式可以一次遍历完成查找;

public List<List<Integer>> threeSum(int[] nums, int target){
	int length = nums.length;
	List<List<Integer>> result = new ArrayList<>();
	Arrays.sort(nums);
	for(int i = 0; i < length - 2; i++) {
		if(nums[i] + nums[i+1] + nums[i+2] > target)break; // too large
		if(nums[i] + nums[length-1] + nums[length-2] < target)continue; // too small
		if(i > 0 && nums[i] == nums[i - 1]) continue;
		int left = i + 1;
		int right = length - 1;
		while(left < right){
		int diff = target - nums[i] - nums[left] - nums[right];
		if (diff == 0){
		result.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
		while(left < right && nums[left] == nums[left + 1]) left++;
		while(left < right && nums[right] == nums[right - 1]) right--;
			left++;
			right--;
		}else if (diff > 0){
		left++;
	}else {
	right--;
	}
	}
	}
	return result;
}

 

 类似资料:
  • Question leetcode: 3Sum | LeetCode OJ lintcode: (57) 3 Sum Problem Statement Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the ar

  • Question leetcode: Two Sum lintcode: Two Sum Problem Statement Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input

  • Question leetcode: 3Sum Closest | LeetCode OJ lintcode: (59) 3 Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the

  • 本文向大家介绍手写代码:LCS问题相关面试题,主要包含被问及手写代码:LCS问题时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 最长公共子序列代码  

  • 返回两个或两个以上数字/数字数组中元素之和。 使用 Array.reduce() 将每个值添加到累加器,并且累加器初始值为 0 。 const sum = (...arr) => [...arr].reduce((acc, val) => acc + val, 0); sum(...[1, 2, 3, 4]); // 10

  • sum

    返回列表中元素的总和。 语法 (Syntax) sum(lst) 参数 (Parameters) Lst - 元素列表。 返回值 (Return Value) 返回列表中元素的总和。 例如 (For example) -module(helloworld). -import(lists,[sum/1]). -export([start/0]). start() -> Lst1 =