import java.util.*; public class PythagoreanTriple { //3Sum approach public ArrayList> findPythagorean(int[] nums) { ArrayList > rst = new ArrayList >(); if (nums == null || nums.length == 0) { return rst; } Arrays.sort(nums); int[] square = new int[nums.length]; for (int i = 0; i < nums.length; i++) { square[i] = nums[i] * nums[i]; } for (int i = 0; i < nums.length - 2; i++) { if (i != 0 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.length - 1; while (left < right) { int sum = square[i] + square[left] - square[right]; if (sum == 0) { ArrayList list = new ArrayList (); list.add(nums[i]); list.add(nums[left]); list.add(nums[right]); rst.add(list); left++; right--; while (left < right && square[left] == square[left - 1]) { left++; } while (right > left && square[right] == square[right + 1]) { right--; } } else if (sum < 0) { right--; } else break; } } return rst; } //backtracking public ArrayList > findPythagorean2(int[] nums) { ArrayList > rst = new ArrayList >(); if (nums == null || nums.length == 0) return rst; ArrayList tri = new ArrayList (); Arrays.sort(nums); findTriangle(rst, tri, nums, 0); return rst; } private void findTriangle(ArrayList > rst, ArrayList tri, int[] nums, int start) { if (tri.size() == 3) { if (tri.get(0) * tri.get(0) + tri.get(1) * tri.get(1) == tri.get(2) * tri.get(2)) { rst.add(new ArrayList (tri)); } return; } for (int i = start; i < nums.length; i++) { if (i != start && nums[i] == nums[i - 1]) continue; tri.add(nums[i]); findTriangle(rst, tri, nums, i + 1); tri.remove(tri.size() - 1); } } }
AdSense
Tuesday, December 23, 2014
Find pythagorean triplets
I am doing this because of this post on Stackoverflow. The question is if there is an O(n) method to do this. Some replies are about using the same approach of 3Sum in LeetCode. I tried both the backtracking way and the 3Sum approach. Based on the code, they are both close to O(n^2) complexity. I tested both, honestly, even the 3Sum can be slightly faster because we trimmed of some iterations, no tremendous improvement.
Labels:
Backtracking
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment