Two Sum
Description
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 would have exactly one solution, and you may not use the same element twice.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution
- 方法一：暴力遍历
1
2
3
4
5
6
7
8
9
10
11
12
13public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
int n=0;
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
res[n++]=i;
res[n++]=j;
}
}
}
return res;
}
时间复杂度：O(n^2)
- 方法二： 利用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度：O(n)
空间复杂度：O(n)
- 方法三：对方法二的改进
1
2
3
4
5
6
7
8
9
10
11public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度：O(n)
空间复杂度：O(n)
3Sum
Description
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.
Note
The solution set must not contain duplicate triplets
Example
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public List<List<Integer>> threeSum(int[] nums){
List<List<Integer>> list = new ArrayList();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
if(i>0 && nums[i]==nums[i-1]) {
continue;
}
int left=i+1;
int right=nums.length-1;
while(left<right) {
if(nums[i]+nums[left]+nums[right]==0) {
list.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
while(left<right && left>0 && nums[left]==nums[left-1]) {
left++;
}
while(left<right && right<nums.length-1 && nums[right]==nums[right+1]) {
right--;
}
}else if(nums[i]+nums[left]+nums[right]<0) {
left++;
}else {
right--;
}
}
}
return list;
}
时间复杂度：O(n^2)
3Sum Closest
Description
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution
解法思路类似于3Sum1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public int threeSumClosest(int[] nums,int target) {
int sum=0,cox=Integer.MAX_VALUE;
int[] rest = new int[3];
Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
int l=i+1;
int r=nums.length-1;
while(l<r) {
sum=nums[i]+nums[l]+nums[r];
int temp=Math.abs(target-sum);
if(temp<cox) {
cox=temp;
rest[0]=nums[i];
rest[1]=nums[l];
rest[2]=nums[r];
}
if(sum==target) {
return sum;
}else if(sum<target) {
l++;
}else {
r--;
}
}
}
return rest[0]+rest[1]+rest[2];
}
时间复杂度O(n^2)
4Sum
Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37public class FourSum {
public List<List<Integer>> fourSum(int[] nums,int target){
List<List<Integer>> list = new ArrayList();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
if(i>0 && nums[i]==nums[i-1]) {
continue;
}
for(int j=i+1;j<nums.length;j++) {
if(j>i+1 && nums[j]==nums[j-1]) {
continue;
}
int l=j+1;
int r=nums.length-1;
while(l<r) {
int sum=nums[i]+nums[j]+nums[l]+nums[r];
if(sum == target) {
list.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
l++;
r--;
while(l<r && l>0 && nums[l] == nums[l-1]) {
l++;
}
while(l < r && r < nums.length && nums[r] == nums[r+1]) {
r--;
}
}else if(sum > target){
r--;
}else {
l++;
}
}
}
}
return list;
}
}
时间复杂度：O(n^3)
Median of Two Sorted Arrays
Description
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example
nums1 = [1, 3]
nums2 = [2]
median is 2.0
Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m=nums1.length;
int n=nums2.length;
if(m>n){
int[] temp=nums1;nums1=nums2;nums2=temp;
int tmp=m;m=n;n=tmp;
}
int iMin=0,iMax=m,hl=(m+n+1)/2;
while(iMin<=iMax){
int i=(iMin+iMax)/2;
int j=hl-i;
if(i<iMax && nums2[j-1]>nums1[i]){
iMin=i+1;
}else if(i>iMin && nums1[i-1]>nums2[j]){
iMax=i-1;
}else{
int maxLeft=0;
if(i==0){
maxLeft=nums2[j-1];
}else if(j==0){
maxLeft=nums1[i-1];
}else{
maxLeft=Math.max(nums1[i-1],nums2[j-1]);
}
if((m+n)%2==1){
return maxLeft;
}
int minRight=0;
if(i==m){
minRight=nums2[j];
}else if(j==n){
minRight=nums1[i];
}else{
minRight=Math.min(nums1[i],nums2[j]);
}
return (maxLeft+minRight)/2.0;
}
}
return 0.0;
}
}