CodePython/3Sum_Practice.py at master · SaiSujithReddy/CodePython · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
'''

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

'''
class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        sorted_nums = sorted(nums)
        #print(sorted_nums)
        final_list = []

        for x in range(len(sorted_nums)-2):
            if sorted_nums[x] >0:
                return final_list
            else:
                # if x > 0 and sorted_nums[x] == sorted_nums[x - 1]:
                #     continue
                y = x + 1
                # while sorted_nums[x] == sorted_nums[y] and y < len(sorted_nums)-2:
                #     y += 1
                z = len(sorted_nums) -1
                target = sorted_nums[x]*-1
                while z > y:
                    if sorted_nums[y] + sorted_nums[z] > target:
                        z -= 1
                    elif sorted_nums[y] + sorted_nums[z] < target:
                        y += 1
                    else:
                        if [sorted_nums[x],sorted_nums[y],sorted_nums[z]] in final_list:
                            pass
                        else:
                            final_list.append([sorted_nums[x],sorted_nums[y],sorted_nums[z]])
                            while sorted_nums[x] == sorted_nums[y] and y < z:
                                y += 1
                            while sorted_nums[x] == sorted_nums[z] and z > y:
                                z -= 1
                        z -= 1
                        y += 1
        return final_list


S = [-1, 0, 1, 2, -1, -4]
#S = [-1, 0, 1, 2,2,2, -1, -4]
#S = [0,0,0]

sol = Solution()
print(sol.threeSum(S))

'''
Complexity
nlogn for sorting
n**n for iterations
n for checking in lists

so finally O(n**2)

'''
'''
Status: Time Limit Exceeded
'''


'''
Things learnt

How to check if an element exists in list

O(n)
if myItem in list:
    # do something

'''