C++, what can I do to speed up my program


  • 0
    Z

    I have used int array to replace map<char, int> and used memset instead of for-loop to initialize int array, but it only beats 80% codes. How to speed it up?

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            const char* str = s.c_str();
            int max_len = 0;
            int idxes[256];
            memset(idxes, -1, 256*sizeof(int));
            register int start_idx = 0;
            register int tmp;
            for (int i = 0; i < s.size(); ++i) {
                tmp = idxes[str[i]];
                if (tmp >= start_idx) {
                    if (max_len < i - start_idx) {
                        max_len = i - start_idx;
                    }
                    start_idx = tmp + 1;
                }
                idxes[str[i]] = i;
            }
            if (max_len < s.size()-start_idx) {
                max_len = s.size()-start_idx;
            }
            return max_len;
        }
    };
    

  • 0
    K

    You can start the position from 1 not 0 to avoid one comparison. I suspect there are lots of shorter test strings, one comparison reducing may improve your result a bit.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.