几道Leetcode上面的数组题目

Posted on | Edited on

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.

思路

使用哈希表存储数据，以实现O(n)的查找复杂度

c++

1
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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,bool> used;
        
        for(auto i:nums) used[i] = false;//冒号的意思是迭代容器nums中的所有元素，元素的临时名字就是i
        
        int longest = 0;
        
        for(auto i:nums){
            if(used[i]) continue;
            
            int length = 1;
            used[i] = true;
            //find()查找函数，若没有找到返回end()
            for(int j = i+1;used.find(j)!=used.end();++j){
                used[j] = true;
                ++length;
            }
            for(int j=i-1;used.find(j)!=used.end();--j){
                used[j] = true;
                ++length;
            }
            longest = max(longest,length);
        }
        return longest;
                
    }
};

python

1
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
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # from sets import Set
        
        s = set()
        ans = 0
        n = len(nums)
        
        #Hash all the nums elements
        for ele in nums:
            s.add(ele)
        
        #check each possible sequence from the start
        #then update optimal length
        for i in range(n):
            #first element 
            if(nums[i]-1) not in s:
                #check for the next element in sequence
                j = nums[i]
                while(j in s):
                    j+=1
                
                #update optimal length 
                ans = max(ans,j-nums[i])
    
        return ans

Two sum

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.

思路

使用散列表来使时间复杂度降到O(n)

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mapping;
        vector<int> result;
        for(int i = 0; i < nums.size();i++){
            mapping[nums[i]] = i;
            
        }
        for(int i = 0;i < nums.size();i++){
            int gap = target - nums[i];
            if(mapping.find(gap) != mapping.end() && mapping[gap] > i){
                result.push_back(i);
                result.push_back(mapping[gap]);
                break;
            }
        }
        return result;
    }
};

Three Sum

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.

思路

左右夹逼，i指针向右走，k指针向左走，j指针在两者之间试探
根据计算的结果，然后调整i，j,k三个指针的位置

c++

1
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<3) return result;
        sort(nums.begin(),nums.end());
        int target = 0;
        
        auto last = nums.end();
        for(auto i = nums.begin();i< last-2;++i){
            auto j =i + 1;
            if(i > nums.begin()&& *i == *(i-1)) continue;
            auto k= last - 1;
            while(j<k){
                if(*i+*j+*k <target){
                    ++j;
                    while(*j==*(j-1)&&j<k)++j;
                }
                else if(*i+*j+*k > target){
                    --k;
                    while(*k == *(k+1)&&j<k)--k;
                }else{
                        result.push_back({*i,*j,*k});
                        ++j;
                        --k;
                        while(*j == *(j-1) && *k==*(k+1)&&j<k) ++j;
                    }
                }
        }
        return result;
        
    }
};

3Sum 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 sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

1
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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int result = 0;
        int min_gap = INT_MAX; //用于存储三数之和和目标的差距
        
        sort(nums.begin(),nums.end());//排序
        
        for(auto a = nums.begin(); a != prev(nums.end(),2);++a){
            auto b = next(a);
            auto c = prev(nums.end());
            while(b < c){
                const int sum = *a + *b + *c;
                const int gap = abs(sum - target);
                
                if(gap < min_gap){
                    result = sum;
                    min_gap = gap;
                }
                
                if(sum < target) ++b;
                else  --c;
            }
        }
        return result;
    }
};

4Sum

Given an array nums of n integers and an integer target,
are there elements a, b, c, and d in nums such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.

思路

使用hashmap缓存两个数的和，但是这种解法实际运行速度较慢

c++

1
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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size()<4) return result;
        sort(nums.begin(),nums.end());
        //使用一个hashmap缓存两个数的和
        unordered_multimap<int,pair<int,int>> cache;
        
        for(int i=0;i+1<nums.size();++i)
            for(int j=i+1;j<nums.size();++j)
                cache.insert(make_pair(nums[i]+nums[j],make_pair(i,j)));
            
        
            for(auto i=cache.begin();i!=cache.end();++i){
                int x = target - i->first;
                auto range = cache.equal_range(x);
                
                for(auto j=range.first;j!=range.second;++j){
                    auto a = i->second.first;
                    auto b = i->second.second;
                    auto c = j->second.first;
                    auto d = j->second.second;
                    if(a != c && a!=d && b!=c && b!=d){
                        vector<int> vec = {nums[a],nums[b],nums[c],nums[d]};
                        sort(vec.begin(),vec.end());
                        result.push_back(vec);
                    }
                    
                }
                        
        }
                sort(result.begin(),result.end());
                result.erase(unique(result.begin(),result.end()),result.end());
                return result;
    }

思路

先排序，然后左右夹逼

c++

1
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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size()<4) return result;
        sort(nums.begin(),nums.end());
        
        auto last = nums.end();
        
        for(auto a = nums.begin();a < prev(last,3);++a)  {
            for(auto b = next(a);b < prev(last,2);++b){
                auto c = next(b);
                auto d = prev(last);
                
                while( c < d){
                    if(*a + *b + *c + *d < target){
                        ++c;
                    }
                    else if(*a + *b + *c + *d >target){
                        --d;
                    }else{
                        result.push_back({*a,*b,*c,*d});
                        ++c;
                        --d;
                    }
                }
            }
        }
        sort(result.begin(),result.end());
        result.erase(unique(result.begin(),result.end()),result.end());
        return result;
    }
};