Google – Good Number

Google – Good Number
一个数如果能用两个立方数相加，并且存在两组这样的立方数，这个数就是一个Good Number.
求小于等于n的所有Good Number.
[Solution]
算是暴力解。
1. 关键点就是先求出小于等于n之内的所有立方数。共有n^(1/3)个立方数。 O(n^(1/3))
2. 然后将这些立方数两两相加求和，并用一个hash table存sum -> count。 O(n^(2/3))
3. 最后扫一遍1到n，如果存在于hash table里并且count大于等于2，就是一个good number。 O(n)
[Time]
总的时间复杂度为O(n^(2/3)), 空间复杂度也为O(n^(2/3))

public List<Integer> goodNumber(int n) {

  List<Integer> result = new ArrayList<>();

 

  List<Integer> cubeNum = new ArrayList<>();

  for (int i = 1; (int) Math.pow(i, 3) <= n; i++) {

    cubeNum.add((int) Math.pow(i, 3));

  }

 

  Map<Integer, Integer> map = new HashMap<>();

  for (int i = 0; i < cubeNum.size(); i++) {

    for (int j = i + 1; j < cubeNum.size(); j++) {

      int sum = cubeNum.get(i) + cubeNum.get(j);

      map.put(sum, map.getOrDefault(sum, 0) + 1);

    }

  }

 

  for (int i = 1; i <= n; i++) {

    if (map.containsKey(i) && map.get(i) >= 2) {

      result.add(i);

    }

  }

 

  return result;

}

Read full article from Google – Good Number