[Li Kou brush questions] 15 Sum of three numbers (double pointer); 17. Letter combination of phone number (recursive backtracking)

Catalog

15. Sum of three numbers

subject ：

Their thinking ：

Code ：

Optimize ：

 17. Letter combination of telephone number

subject ：

​ Editing problem solving ideas ：

Code ：

---

15. Sum of three numbers

subject ：

Give you one containing n Array of integers  nums, Judge  nums  Are there three elements in a,b,c , bring  a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/3sum
 

Their thinking ：

Give me an array , Determine whether the sum of three elements is equal to 0, Find all triples of non repeating elements . I began to think that since I didn't want to repeat , Then use the hash table to determine whether it contains a triple , If so, don't add it to the answer , If not, join . Because it's a triple , To select three elements from the array , Those with the highest time complexity also need O（n³）, Optimize it again ： First floor for After the loop, the other two elements use double pointers （ When two of these elements are fixed a and b after , The remaining element c Must be the only one a+b+c=0, So you can sort + Double pointer to achieve ） To choose , That's it O（n²）, You need to sort the array directly first , Sorting time complexity is also O（n²）. So the time complexity of this topic is O（n²）.

Because the array elements will be sorted , Use a layer for The loop fixes an element a after , The rest b and c It must move towards the middle of the array , Until the left and right pointers meet . When a+b+c=0 when , When a pointer moves , The other pointer must also move ,left++ and right--;>0, Move the right pointer to the left , Turn down the positive number right--;<0, Move the left pointer to the right , Turn up that negative number left++.

Code ：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length < 3) return new LinkedList<>();
        // Sort the array 
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        // Use hash table to judge duplication 
        HashMap<List<Integer>,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length - 2;i++){
            // Double pointer 
            int left = i + 1,right = nums.length - 1;
            while(left < right){
                if(nums[i]+nums[left]+nums[right] == 0){
                    List<Integer> list = new LinkedList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    if(map.containsKey(list)){
                        left++;
                        right--;
                        continue;
                    }else{
                        map.put(list,1);
                        res.add(list);
                        left++;
                        right--;
                    }
                }else if(nums[i]+nums[left]+nums[right] > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return res;
    }
}

And found that , Only defeated 5.29% Ha ha ha ha ha ha .

Optimize ：

Then optimized , In fact, this problem does not need to use the hash table to determine the weight , Because after using sorting , Repeated elements will be next to each other , I have selected the last cycle , Then there is no need to select the same elements again , Just skip it .

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length < 3) return new LinkedList<>();
        // Sort the array 
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        for(int i = 0; i < nums.length - 2;i++){
            // Continuous same elements , Selected , Just skip 
            if(i>0 && nums[i] == nums[i-1]) continue;
            // Double pointer 
            int left = i + 1,right = nums.length - 1;
            while(left < right){
                // Continuous same elements , Selected , jump 
                if(left > i + 1 && nums[left] == nums[left - 1]) {
                    left++;
                    continue;
                }
                if(nums[i]+nums[left]+nums[right] == 0){
                    List<Integer> list = new LinkedList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    left++;
                    right--;
                }else if(nums[i]+nums[left]+nums[right] > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return res;
    }
}

 17. Letter combination of telephone number

subject ：

Their thinking ：

Because I don't know how many digits it will contain , So it's not sure how many layers to use for loop , So I thought of recursion + Backtracking to achieve , Much like solving mazes .

Save the string corresponding to each number , Just use 0 and 1 There is no corresponding character , So the numbers 2-9 Directly corresponding to subscript 2-9. Save the answer with a global class variable .

dfs Method parameters ：digits character string ,digits The length of , Which number is currently traversed （ End ：count==n）, Answer string .

The code is easy to write , Pay attention to backtracking .

            ans += cur.charAt(i);
            dfs(digits,n,count + 1,ans);
            // to flash back 
            ans = ans.substring(0,ans.length()-1);

Code ：

class Solution {
    String[] s = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> res = new LinkedList<String>();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return new LinkedList<String>();
        int n = digits.length();
        dfs(digits,n,0,"");
        return res;
    }
    // Parameter is ①digits,②digits The length of ,③ Currently, several numbers have been traversed ( from 0 Start , Join in res The judgment of count==n),④ Answer string 
    public void dfs(String digits,int n,int count,String ans){
        // The end of recursion 
        if(count == n){
            res.add(ans);
            return;
        }
        int index = Integer.parseInt(""+digits.charAt(count));
        String cur = s[index];
        for(int i = 0; i < cur.length();i++){
            ans += cur.charAt(i);
            dfs(digits,n,count + 1,ans);
            ans = ans.substring(0,ans.length()-1);
        }
    }
}

ovo Why is it so low every time , But no GUAXI , Come on, hahahaha