카테고리 없음
three sum - leet code
Sumin Lim
2020. 3. 27. 22:29
반응형
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
import java.util.List;
public class Model {
private static List<List<Integer>> threeSum(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
for(int k = 0; k<nums.length; k++) {
if (i != j && j != k && i != k)
System.out.println(i + ", " + j +", " +k);
}
}
}
return null;
}
public static void main(String[] args) {
int[] nums = { -1, 0, 1, 2, -1, -4 };
threeSum(nums);
}
}
| 0, 1, 2 <- 0, 1, 3 0, 1, 4 0, 1, 5 0, 2, 1 <- 중복 발생, 문제는 중복순열이 아닌 그냥 순열을 구하는 문제임... 0, 2, 3 0, 2, 4 0, 2, 5 0, 3, 1 0, 3, 2 0, 3, 4 0, 3, 5 0, 4, 1 0, 4, 2 0, 4, 3 0, 4, 5 0, 5, 1 0, 5, 2 0, 5, 3 0, 5, 4 1, 0, 2 1, 0, 3 1, 0, 4 1, 0, 5 1, 2, 0 1, 2, 3 1, 2, 4 1, 2, 5 1, 3, 0 1, 3, 2 1, 3, 4 1, 3, 5 1, 4, 0 1, 4, 2 1, 4, 3 1, 4, 5 1, 5, 0 1, 5, 2 1, 5, 3 1, 5, 4 2, 0, 1 2, 0, 3 2, 0, 4 2, 0, 5 2, 1, 0 2, 1, 3 2, 1, 4 2, 1, 5 2, 3, 0 2, 3, 1 2, 3, 4 2, 3, 5 2, 4, 0 2, 4, 1 2, 4, 3 2, 4, 5 2, 5, 0 2, 5, 1 2, 5, 3 2, 5, 4 3, 0, 1 3, 0, 2 3, 0, 4 3, 0, 5 3, 1, 0 3, 1, 2 3, 1, 4 3, 1, 5 3, 2, 0 3, 2, 1 3, 2, 4 3, 2, 5 3, 4, 0 3, 4, 1 3, 4, 2 3, 4, 5 3, 5, 0 3, 5, 1 3, 5, 2 3, 5, 4 4, 0, 1 4, 0, 2 4, 0, 3 4, 0, 5 4, 1, 0 4, 1, 2 4, 1, 3 4, 1, 5 4, 2, 0 4, 2, 1 4, 2, 3 4, 2, 5 4, 3, 0 4, 3, 1 4, 3, 2 4, 3, 5 4, 5, 0 4, 5, 1 4, 5, 2 4, 5, 3 5, 0, 1 5, 0, 2 5, 0, 3 5, 0, 4 5, 1, 0 5, 1, 2 5, 1, 3 5, 1, 4 5, 2, 0 5, 2, 1 5, 2, 3 5, 2, 4 5, 3, 0 5, 3, 1 5, 3, 2 5, 3, 4 5, 4, 0 5, 4, 1 5, 4, 2 5, 4, 3 |
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Model {
private static List<List<Integer>> threeSum(int[] nums) {
List< List<Integer>> res = new ArrayList< List<Integer>>();
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
for (int k = 0; k < nums.length; k++) {
if (i != j && j != k && i != k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
int arr []= {nums[i], nums[j], nums[k]};
Arrays.sort(arr);
List<Integer> w = new ArrayList<Integer>();
w.add(arr[0]);
w.add(arr[1]);
w.add(arr[2]);
if (res.size() == 0 || !isExist(res, w) ) {
res.add(new ArrayList(w));
}
}
}
}
}
}
return res;
}
private static boolean isExist(List<List<Integer>> res, List<Integer> w) {
boolean res1=false;
for (int b=0; b< res.size() && res.size() >0; b++) {
List<Integer> tar = res.get(b);
// System.out.print(w.get(0) + ", " + w.get(1) + ", " + w.get(2));
// System.out.print(" vs "+tar.get(0)+", "+tar.get(1)+", "+tar.get(2));
boolean condition = (tar.get(0)==w.get(0) )&&( tar.get(1)== w.get(1) )&&( tar.get(2) == w.get(2));
if ( condition) {
return true;
}
else {res1 = false;
//System.out.println(" >>");
}
}
return res1;
}
public static void main(String[] args) {
int[] nums = { -1, 0, 1, 2, -1, -4 };
List<List<Integer>> a = threeSum(nums);
System.out.println(a.size());
}
}
아래의 경우에 time limit이 난다...
[-12,0,6,-13,-7,-15,-6,-6,-2,-14,-2,14,1,11,-12,-11,-2,-6,7,2,-5,-9,-11,-13,9,-7,-8,9,-12,-1,5,14,14,-3,8,14,-3,-13,-14,3,10,-1,2,-3,-13,-3,-7,-7,-2,-15,2,8,-9,7,2,8,7,2,2,11,-14,-8,2,7,-4,-5,7,9,-11,0,-11,-15,14,6,-11,9,-11,-3,9,-6,-11,-4,-12,-4,10,5,11,-5,-8,-2,13,-7,-3,0,-14,1,10,0,-5,6,-15,-1,6,6]
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Model {
private static List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
for (int i = 0; i < num.length - 2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i - 1])) {
int lo = i + 1, hi = num.length - 1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo + 1])
lo++;
while (lo < hi && num[hi] == num[hi - 1])
hi--;
lo++;
hi--;
} else if (num[lo] + num[hi] < sum)
lo++;
else
hi--;
}
}
}
return res;
}
public static void main(String[] args) {
int[] nums = { -1, 0, 1, 2, -1, -4 };
List<List<Integer>> a = threeSum(nums);
System.out.println(a.size());
}
}
반응형