[Leet Code] 15. 3Sum 다시 공부 ★

3Sum

 

 문제 설명

 

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

 제한 사항

 

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

 

 입출력 예

Example 1:

Input : num = [-1, 0, 1, 2, -1, -4]
Output : [[-1, -1, 2], [-1, 0, 1]]

Example 2:

Input : nums = []
Output : []

Example 3:

Input : nums = [0]
Output : []

 

 Python 코드

 

Python 8ms code 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
class Solution(object):
    def isSameTree(self, p, q):
     
        if not p and not q:
            return True
        if not p or not q:
            return False
        
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

•  

* 참고 링크 : 

 

 C++ 코드

 

C ++ 100% 0ms code

- String으로 바꾸지 않고 맨 뒤의 값과 맨 앞의 값을 비교하면서 푼 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) // if the two nodes are empty nodes, return true
            return true;
        else if((p == NULL && q != NULL) || (p != NULL && q == NULL)) // if only one of the nodes from p and q is emtpy, 2 trees are not equal
            return false;
        else 
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
						// First we compare the values in each node from p and q. Then, use a recursive method, call isSameTree function with left nodes of p and q as parameters. Do the same for the right nodes.
    }
};

* 참고 링크 : 

 

 출처

 

https://leetcode.com/problems/3sum/