3sumV3.dart (2270B)
1 //Three sum solution using dart and two pointers. 2 //The first thing done was I sorted the list to make sure 3 //I would not be checking the same value multiple times, and it allows for 4 //the two pointer optimization. The two pointer optimization is the main secret for this problem. 5 //This allows for the time complexity of this code to be O(n^2) instead of n^3. 6 //Basically what it does is it checks to see if the left and right values add up to 7 //the needed value based on the first. An example would be if the first value is 5 8 //then the second and third would need to add up to -5. If the value the left and right add 9 //up to is bigger than that then you move the right pointer to the left and if the value 10 //is higher than the current value then you move the left pointer to the right. 11 //By doing this you no longer have to check if each set of two adds up to the value. 12 //Time: 405ms Beats: 60% 13 //Memory: 157.7MB Beats: 27.14% 14 15 class Solution { 16 List<List<int>> threeSum(List<int> nums) { 17 Set<String> found = {}; 18 nums.sort(); 19 List<List<int>> return_list = []; 20 int last_val = 1000000; 21 for(int i = 0 ; i < nums.length ; ++i){ 22 if(nums[i]== last_val){ 23 continue; 24 } 25 int current = nums[i]; 26 last_val = current; 27 int left = i + 1; 28 int right = nums.length - 1; 29 int val_to_find = (current) * -1; 30 while(left < right){ 31 if(nums[left] + nums[right] > val_to_find){ 32 right -= 1; 33 continue; 34 } 35 if(nums[right] + nums[left] < val_to_find){ 36 left += 1; 37 continue; 38 } 39 if(nums[right] + nums[left] == val_to_find){ 40 String current_lst = current.toString() + " " + nums[left].toString() + " " + nums[right].toString(); 41 if(found.contains(current_lst) == false){ 42 found.add(current_lst); 43 return_list.add([current , nums[left] , nums[right]]); 44 left += 1; 45 continue; 46 } 47 left += 1; 48 continue; 49 } 50 } 51 } 52 return return_list; 53 } 54 }