3sumV2.dart (1964B)
1 //3 sum solution using hashmap to check if the final value exists 2 //so that O(n^2) time complexity can be achieved instead of O(n^3) 3 4 class Solution { 5 Set<String> set_strs = {}; 6 Map<int, int> vals = {}; 7 List<List<int>> threeSum(List<int> nums) { 8 for(int i = 0 ; i < nums.length ; ++i){ 9 vals[nums[i]] = (vals[nums[i]] ?? 0) + 1; 10 } 11 List<List<int>> all_perm = permutations(nums); 12 return all_perm; 13 } 14 List<List<int>> permutations(List<int> nums){ 15 List<List<int>> return_list = []; 16 for(int i = 0 ; i < nums.length ; ++i){ 17 for(int x = i + 1; x < nums.length ; ++x){ 18 int val_needed = (nums[i] + nums[x]) * -1; 19 if(vals.containsKey(val_needed)){ 20 List<int> current =[nums[i] , nums[x] , val_needed]; 21 current.sort(); 22 String current_str = ""; 23 for(int i = 0 ; i < current.length ; ++i){ 24 current_str += current[i].toString() + " "; 25 } 26 if(set_strs.contains(current_str)){ 27 continue; 28 } 29 set_strs.add(current_str); 30 List<int> dupes = []; 31 if(current[0] == current[1] && current[1] == current[2]){ 32 dupes.add(current[0]); 33 dupes.add(current[0]); 34 dupes.add(current[0]); 35 } 36 else if(current[0] == current[1]){ 37 dupes.add(current[0]); 38 dupes.add(current[0]); 39 } 40 else if(current[0] == current[2]){ 41 dupes.add(current[0]); 42 dupes.add(current[0]); 43 } 44 else if(current[2] == current[1]){ 45 dupes.add(current[2]); 46 dupes.add(current[2]); 47 } 48 49 if(dupes.length > 0){ 50 if(dupes.length > (vals[dupes[0]] ?? 0 )){ 51 continue; 52 } 53 } 54 return_list.add(current); 55 } 56 } 57 } 58 return return_list; 59 } 60 }